【LeetCode 刷题】回溯算法(2)-分割问题

此博客为《代码随想录》二叉树章节的学习笔记，主要内容为回溯算法分割问题相关的题目解析。

131.分割回文串

题目链接

class Solution:def partition(self, s: str) -> List[List[str]]:res, path = [], []def check(s: str) -> bool:left, right = 0, len(s) - 1 while left < right:if s[left] != s[right]:return Falseleft += 1right -= 1return Truedef dfs(start: int) -> None:if start == len(s):res.append(path.copy())returnfor i in range(start, len(s)):if check(s[start:i+1]):path.append(s[start:i+1])dfs(i + 1)path.pop()dfs(0)return res

• dfs 的参数为当前子串的起始位置，之后枚举子串的结束位置
• 双指针法判断是否为回文串，也可直接使用 t == t[::-1] 判断

93.复原IP地址

题目链接

class Solution:def restoreIpAddresses(self, s: str) -> List[str]:res, path = [], []def check(s: str) -> bool:if not s.isdigit():return Falseif len(s) > 1 and s[0] == '0':  # 含有前导零return Falsereturn 0 <= int(s) <= 255def dfs(start: int) -> None:if start == len(s) and len(path) == 4:res.append('.'.join(path))returnif len(path) == 4:returnfor i in range(start, len(s)):if check(s[start:i+1]):path.append(s[start:i+1])dfs(i + 1)path.pop()dfs(0)return res

• 添加对分割次数的限制，即只能分割为四段
• check() 函数的逻辑需根据题目要求编写，其他逻辑与上题的分割过程基本一致