Leetcode 回溯—分割篇

Leetcode刷题记录——回溯分割篇

Leetcode131 分割回文串

抽象

递归用来纵向遍历，for循环用来横向遍历，切割到字符串的结尾位置，说明找到了一个切割方法

Python代码如下

class Solution:
    def __init__(self):
        self.res = []
        self.path = []
    def backtracking(self, s, startIndex):
        if startIndex == len(s):
            self.res.append(self.path[:])
            return
        for i in range(startIndex, len(s)):
            if self.isHuiwen(s[startIndex:i+1]):
                self.path.append(s[startIndex:i+1])
                self.backtracking(s, i+1)
                self.path.pop()
            else:
                continue
    def isHuiwen(self, s):
        left = 0
        right = len(s)-1
        while left < right:
            if s[left] != s[right]:
                return False
            left += 1
            right -= 1
        return True 
    def partition(self, s: str) -> List[List[str]]:
        self.backtracking(s, 0)
        return self.res

Leetcode93 复原IP地址

分割的思想与分割回文串一致

这道题的终止条件，以及子串的合法性需要多加注意

Python代码如下

class Solution:
    def __init__(self):
        self.res = []
        self.path = []
    def restoreIpAddresses(self, s: str) -> List[str]:
        self.backtracking(s, 0)
        return self.res
    def backtracking(self, s, startIndex):
        # path长度为4, 且startIndex到达s尾部时, 收集path
        if len(self.path) == 4 and startIndex == len(s):
            self.res.append('.'.join(self.path[:]))
            return
        # path长度超过4时, 上面已经不成立了, 所以可以有等号
        if len(self.path) >= 4:
            return
        for i in range(startIndex, len(s)):
            # startIndex是分割起始位置, i是当前遍历位置, 确保长度要小于3, 不写也行, 下面合法会判断
            if i - startIndex < 3 and self.isValid(s[startIndex:i+1]):
                self.path.append(s[startIndex:i+1])
                self.backtracking(s, i+1)
                self.path.pop()
    # 子串合法的判断函数
    def isValid(self, s):
        if len(s) == 0 or (s[0] == '0' and len(s) > 1):
            return False
        num = int(s)
        return 0 <= num <= 255