题目:93. 复原IP地址
给定一个只包含数字的字符串,复原它并返回所有可能的 IP 地址格式。 有效的 IP 地址正好由四个整数(每个整数位于 0 到 255 之间组成),整数之间用 '.' 分隔。 示例: 输入: "25525511135" 输出: ["255.255.11.135", "255.255.111.35"]
解题:
1、类似于DFS回溯解法。
代码:
class Solution(object):
# 判断是否有效
def isValid(self, s):
if len(s) >1 and s[0] == '0':
return False
if 0 <= int(s) <= 255:
return True
return False
def split(self, s, start, num, current):
# 数字长度是否满足要求
if len(s) - start < num or len(s) - start > 3 * num:
return
# 只有一位时,判断是否有效
if num == 1:
if self.isValid(s[start:]):
current2 = copy.copy(current)
current2.append(s[start:])
self.res.append('.'.join(current2))
return
# 其他情况,split
for i in range(start + 1, len(s) - num + 2):
if self.isValid(s[start: i]):
current2 = copy.copy(current)
current2.append(s[start: i])
self.split(s, i, num - 1, current2)
else:
break
def restoreIpAddresses(self, s):
"""
:type s: str
:rtype: List[str]
"""
self.res = []
self.split(s, 0, 4, [])
return self.res