131. 分割回文串

题目

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

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

示例 1：

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

示例 2：

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

提示：

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

解答

思路：答案视角

枚举 aab 的所有子串，可以看作是枚举 "a, a, b" 的这两个逗号，选/不选：

["aab"]
["a", "ab"]
["aa", "b"]
["a", "a", "b"]

回溯三问：

• 当前操作：枚举逗号的位置，选择回文子串 s[i..j] 加入 path
• 当前问题：从下标 $\ge i$ 的 后缀 中构造回文分割
• 它的子问题：从下标 $\ge j+1$ 的 后缀 中构造回文分割

可以认为 dfs(i) 的目标就是找一个回文串 s[i..j]，因为它只需要考虑 $\ge i$ 的 后缀，而 $\ge j+1$ 的 后缀 已经由 dfs(j + 1) 构造好了回文分割。

怎么判断回文串？相向双指针即可。看似暴力判断回文，实则如果我们把判断这一步放到加入 ans 前，那么由于所有串的长度加起来为 $n$，因此判断的时间复杂度加起来也是 $O(n)$ 的。

• 时间复杂度为 $O(n{2}^n)$
• 空间复杂度为 $O(n)$

代码

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        ans = []
        path = []
        n = len(s)

        def dfs(i):
            if i == n:
                ans.append(path.copy())
                return
            
            for j in range(i, n):
                t = s[i: j + 1]
                
                if t == t[::-1]:
                    path.append(t)
                    dfs(j + 1)
                    path.pop()
            
        dfs(0)
        return ans

思路：输入视角

代码

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        ans = []
        path = []
        n = len(s)

        # start 表示当前这段回文子串的开始位置
        def dfs(i: int, start: int) -> None:
            if i == n:
                ans.append(path.copy())
                return

            # 不选 i 和 i+1 之间的逗号（i=n-1 时一定要选）
            if i < n - 1:
                dfs(i + 1, start)

            # 选 i 和 i+1 之间的逗号（把 s[i] 作为子串的最后一个字符）
            t = s[start: i + 1]
            if t == t[::-1]:
                path.append(t)
                dfs(i + 1, i + 1)  # 下一个子串从 i+1 开始
                path.pop()

        dfs(0, 0)
        return ans