93.复原IP地址
1、方法一
class Solution:
def restoreIpAddresses(self, s: str) -> List[str]:
res = []
self.tracebacking(s, 0, [], res)
return res
def tracebacking(self, s, start, path, res):
if start == len(s) and len(path) == 4: # 刚好分割为 4 份
res.append(".".join(path[:]))
return
if len(path) > 4: # 剪枝
return
for i in range(start, len(s)):
if self.isValidIp(s, start, i):
path.append(s[start:i+1])
self.tracebacking(s, i+1, path, res)
path.pop()
def isValidIp(self, s, start, end): # 判断是否合法
if start > end:
return False
for i in range(start, end+1):
if not s[i].isdigit():
return False
if int(s[start]) == 0 and start != end:
return False
return 0<=int(s[start:end+1])<=255
2、方法二
class Solution:
def restoreIpAddresses(self, s: str) -> List[str]:
res = []
self.tracebacking(s, 0, 0, [], res)
return res
def tracebacking(self, s, start, point, path, res):
if point == 3:
if self.isValidIp(s, start, len(s)-1):
path.append(s[start:])
res.append("".join(path[:]))
# 回溯，这里容易忘记
path.pop()
return
for i in range(start, len(s)):
if self.isValidIp(s, start, i):
sub = s[start:i+1]
path.append(sub)
path.append(".")
point += 1
self.tracebacking(s, i+1, point, path, res)
# 回溯
point -= 1
path.pop()
path.pop()
def isValidIp(self, s, start, end): # 判断是否合法
if start > end:
return False
for i in range(start, end+1):
if not s[i].isdigit():
return False
if int(s[start]) == 0 and start != end:
return False
return 0<=int(s[start:end+1])<=255
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
res = []
self.tracebacking(nums, 0, [], res)
return res
def tracebacking(self, nums, start, path, res):
res.append(path[:])
if start > len(nums)-1:
return
for i in range(start, len(nums)):
path.append(nums[i])
self.tracebacking(nums, i+1, path, res)
path.pop()
class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
res = []
nums.sort()
self.tracebacking(nums, 0, [], res)
return res
def tracebacking(self, nums, start, path, res):
res.append(path[:])
if start > len(nums) - 1:
return
for i in range(start, len(nums)):
if i > start and nums[i] == nums[i-1]:
continue
path.append(nums[i])
self.tracebacking(nums, i+1, path, res)
path.pop()