131. 分割回文串 Medium

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

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

示例 2:
输入：s = "a"
输出：[["a"]]

解题思路

输入：一个字符串 s

输出：将 s 分割成一些字串，所有字串都是回文串，返回 s 所有可能的分割方案

这道题属于子集型回溯问题。

• 我们可以从左到右，把字符串的每个位置都尝试分割。
• 每次分割后，把左边那段拿出来，判断是不是回文串。
• 如果是，就把它加到当前的分割方案里（放到 path 里）。
• 然后继续递归处理剩下的部分。
• 如果处理到字符串的末尾，就说明找到了一种有效的分割方案，把它保存到答案里（放到 ans 里）。

回溯三问

1. 当前操作？

   • 在当前位置 i，尝试从 s[i:j+1] 中截取一个子串 t。
   • 检查这个子串 t 是否是回文串，如果是，则把它加入到路径 path 中。
   • 也就是把符合条件的回文子串放到路径里，表示“我选择了这部分子串”。

2. 子问题？

   • 在选择了回文子串 t 之后，需要继续递归处理剩余的字符串。
   • 也就是从 j+1 位置开始，继续往下分割剩下的子串。

3. 下一个子问题？

   • 下一步递归就是 dfs(j+1)，表示从 j+1 开始分割剩余的字符串。
   • 继续往下构造所有可能的分割路径。

剪枝条件

• 只有当 s[i:j+1] 是回文串时，才把它加入路径并递归继续分割；如果不是回文串就直接跳过，不再递归。

代码实现

python

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]  # 截取子串 s[i..j]

                # 检查子串是否是回文串
                if t == t[::-1]:
                    path.append(t)    # 如果是回文串，则将其加入路径
                    dfs(j + 1)        # 继续递归，分割剩余的子串
                    path.pop()        # 回溯，移除最后一个子串

        dfs(0)  # 从索引 0 开始递归
        return ans

javascript

/**
 * @param {string} s
 * @return {string[][]}
 */
const partition = function(s) {
    const ans = [];
    const path = [];

    function dfs(i) {
        if (i == s.length) {
            ans.push([...path]);
            return;
        }

        for (let j = i; j < s.length; j++) {
            const sub = s.slice(i, j + 1);
            const backSub = sub.split('').reverse().join('');

            if (sub == backSub) {
                path.push(sub);
                dfs(j + 1);
                path.pop();
            }
        }
    }
    dfs(0);
    return ans;
};

复杂度分析

时间复杂度：O(n * 2^n)

空间复杂度：O(n * 2^n)

链接

131 国际版

131 中文版