代码随想录算法训练营day27 | 93.复原IP地址、78.子集、90.子集II

93.复原IP地址

和C++不同，使用列表存储已经分割的数据，而不是直接操作字符串。为了使用这个列表搞了老久，主要问题出在，在判断终止条件的时候，path也需要回溯一下

class Solution:def __init__(self):self.result = []self.path = []def is_valid_ip(self, s, start, end):if start > end:return False# 不能以0开头if s[start] == '0' and start != end:return False# 不能含有非法字符num = 0for letter in s[start:end+1]:if letter < '0' and letter > '9':return Falsenum = num * 10 + int(letter)# 不能超过255if num > 255:return Falsereturn Truedef backtracking(self, s, startIndex, pointNum):if pointNum == 3:if self.is_valid_ip(s, startIndex, len(s)-1):self.path.append(s[startIndex:])self.result.append(".".join(self.path))self.path.pop()returnfor i in range(startIndex, len(s)):if self.is_valid_ip(s, startIndex, i):self.path.append(s[startIndex:i+1])pointNum += 1self.backtracking(s, i+1, pointNum)self.path.pop()pointNum -= 1else:break  # 本次数值不合法，下一次也不会合法，看看合法的条件就可明白def restoreIpAddresses(self, s: str) -> List[str]:if len(s) < 4 or len(s) > 12:return self.resultself.backtracking(s, 0, 0)return self.result

78.子集

子集问题是收集树的所有节点

class Solution:def __init__(self):self.result = []self.path = []def backtracking(self, nums, startIndex):self.result.append(self.path[:])# 终止条件可不写if startIndex >= len(nums):returnfor i in range(startIndex, len(nums)):self.path.append(nums[i])self.backtracking(nums, i+1)self.path.pop()def subsets(self, nums: List[int]) -> List[List[int]]:self.backtracking(nums, 0)return self.result

90.子集II

和之前做的一样，树结构的层级遍历不能重复，纵向可以重复

class Solution:def __init__(self):self.result = []self.path = []def backtracking(self, nums, startIndex):self.result.append(self.path[:])# 终止条件可以忽略不写，因为for循环直接就退出了for i in range(startIndex, len(nums)):if i > startIndex and nums[i] == nums[i-1]:continueself.path.append(nums[i])self.backtracking(nums, i+1)self.path.pop()def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:# 需要先排序nums.sort()self.backtracking(nums, 0)return self.result