[Python] 纯文本查看 复制代码
class Solution:
def restoreIpAddresses(self, s: str) -> List[str]:
length = len(s)
if length < 4 or length > 12:
return []
res = []
self.__dfs(s, 0, length, [], res)
return res
def __dfs(self, s, start, length, path, res):
blank = 4 - len(path)
if blank == 0:
if start >= length:
res.append(".".join(path.copy()))
return
if (length - start < blank) or (length - start > 3 * blank):
# 剩下的数字比空还少 或 比3*空还多
return
for i in range(1, 4):
end = start + i
if end > length or int(s[start:end]) > 255 or (i > 1 and s[start:end][0] == "0"):
# 不合法：超过255、非单个数字且首位为0
break
path.append(s[start:end])
self.__dfs(s, end, length, path, res)
path.pop()