131. 分割回文串

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

回文串 是正着读和反着读都一样的字符串。

 

示例 1：

输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]
示例 2：

输入：s = "a"
输出：[["a"]]
 

提示：

1 <= s.length <= 16
s 仅由小写英文字母组成

分析

这是一种切割问题，切割问题类似组合问题
主要的难点是寻找切割线，终止条件很容易得到就是：切割线与字符串的长度相等时，切割结束。
for循环是切割线的变动，即从start到字符串长度减1（实际上就是遍历字符串的范围），递归的话由于不要求重复就递归i+1即可。
判定回文也很简单，左右指针设定下去问题很容易解决，实在不行就反转，判定是否相等。
添加到path里面就是切割线start到i，start相当于是前一个切割线的后一位数据，i相当于是下一个切割线，所以递归i+1，也是为了将i+1替换成下一个start。

代码

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        res = []
        path = []
        
        def huiwen(s): # 返回值bool，判断是否是回文串
            left,right = 0,len(s)-1
            while left < right:
                if s[left] != s[right]:
                    return False
                left+=1
                right-=1
            return True                

        def backtrack(start):
            if start == len(s):
                res.append(path[:])
                return

            for i in range(start,len(s)):
                if huiwen(s[start:i+1]):
                    path.append(s[start:i+1])
                else:
                    continue
                backtrack(i+1)
                path.pop()

        backtrack(0)
        return res

通过截图

在这里插入图片描述

93. 复原 IP 地址

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

例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。
给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你不能重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。


示例 1：

输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]
示例 2：

输入：s = "0000"
输出：["0.0.0.0"]
示例 3：

输入：s = "1111"
输出：["1.1.1.1"]
示例 4：

输入：s = "010010"
输出：["0.10.0.10","0.100.1.0"]
示例 5：

输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
 

提示：

0 <= s.length <= 20
s 仅由数字组成

分析

由题意可知，超过12位数绝对无解
该题也是切割问题，但需要判定是否存在前导0，我们只需要看数字的长度只要大于1且第一位不为0即可确定，没有前导0。大于一位数只能说明这是多位数（可能是000），为了避免这种情况发生还需要看第一位是什么。
其他和上一题切割问题一样

代码

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

        if len(s)>12:
            return res
        def effect(s):
            if s[0] == '0' and len(s)>1: # 第一位为0，但是长度大于1，说明这个数前导0 
                return False
            s = int(s)
            if s < 0 or s > 255:
                return False
            return True

        def backtrack(start):
            if start == len(s):
                if len(path) == 4:
                    res.append(".".join(path))
                return
                
            if len(path) > 4 :
                return

            for i in range(start,len(s)):
                if effect(s[start:i+1]): # 切割有效
                    path.append(s[start:i+1])
                else:
                    continue
                
                backtrack(i+1)
                path.pop()

        backtrack(0)
        return res