131.分割回文串

link

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串。返回 s 所有可能的分割方案。

思路

类似于组合问题，也可以抽线成一棵树

递归参数：当前字符串的起始位置
结束条件：遍历到字符串末尾就结束，并将 cur 加入 res。（递归逻辑中保证当前 cur 一定是满足条件的）
递归逻辑：如果当前子串是回文串则加入 cur，并且向下递归。注意，如果当前子串不是回文串则直接剪枝，不进行后续步骤。（保证当前 cur 一定是满足条件的）

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        res = []
        cur = []

        def ishuiwen(start, end):
            while start <= end:
                if s[start] != s[end]:
                    return False
                start += 1
                end -= 1
            return True

        def backtrack(start):
            if start == len(s):
                res.append(cur[:])
                return
            
            for i in range(start, len(s)):
                if ishuiwen(start, i):
                    cur.append(s[start:i+1])
                    backtrack(i+1)
                    cur.pop()   

        backtrack(0)
        return res

93.复原IP地址

link

有效 IP 地址正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 ‘.’ 分隔

思路

递归的逻辑中，由于 ip 地址最长为 3 位，所以 for 循环只需要循环三次，但是要考虑到不能超过 s 的长度，所以 range 的结束点为 min(start + 3, len(s))。

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        res = []
        cur = []

        def isvad(subs):
            num = int(subs)
            if num == 0 and len(subs) == 1:
                return True
            if num == 0 and len(subs) > 1:
                return False
            elif subs[0] == '0':
                return False
            elif num > 255:
                return False
            else:
                return True
        
        def backtrack(start):
            if start == len(s) and len(cur) == 4:
                res.append(".".join(cur))
                return
            if len(cur) > 4:
                return
            
            for i in range(start, min(start + 3, len(s))):
                if isvad(s[start:i+1]):
                    cur.append(s[start:i+1])
                    backtrack(i+1)
                    cur.pop()
        backtrack(0)
        return res