当前位置：首页 > article >正文

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

article 2025/2/4 2:56:21

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

文章目录

131.分割回文串
93.复原IP地址

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 False
                left += 1
                right -= 1
            return True

        def dfs(start: int) -> None:
            if start == len(s):
                res.append(path.copy())
                return
            for 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 False
            if len(s) > 1 and s[0] == '0':  # 含有前导零
                return False
            return 0 <= int(s) <= 255
        
        def dfs(start: int) -> None:
            if start == len(s) and len(path) == 4:
                res.append('.'.join(path))
                return
            if len(path) == 4:
                return
            for 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