93. Restore IP Addresses
给你一串数字组成的字串，要你输出它可能是那些 IP
IP的规则: 共四个 0~255 的数字，中间以 '.' 隔开
Example 1:
Input: s = "25525511135"
Output: ["255.255.11.135","255.255.111.35"]
Example 2:
Input: s = "0000"
Output: ["0.0.0.0"]
Example 3:
Input: s = "101023"
Output: ["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
思路:
1.和昨天很像的 DFS，往后尝试切长度为 1~3 的字串(因为最高是 255)
然后检查它有没有在 0~255 内 有的话就塞进参数的 array 里往下传
碰到结尾时数字刚好有四个就成功 否则失败
碰到 0 时可以直接切 因为非零数字不能以 0 开头所以他只能是 0
Python code:
class Solution:
def restoreIpAddresses(self, s: str) -> List[str]:
n = len(s)
res = []
def dfs(idx, arr, length):
if length == 4 and idx == n:
res.append('.'.join(arr))
if length == 4 or idx == n:
return
if s[idx] == '0':
dfs(idx+1, arr+['0'], length+1)
else:
for i in range(idx+1, min(idx+3, n)+1):
num = s[idx:i]
if int(num) <= 255:
dfs(i, arr+[num], length+1)
dfs(0, [], 0)
return res
刷题帮DC: https://discord.gg/8Gqm9Z2t

大师

大师