LC 131. 分割回文串

题目描述

这是 LeetCode 上的 131. 分割回文串 ，难度为中等。

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串。

返回 s 所有可能的分割方案。

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

示例 1：

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

示例 2：

1 2	`输入：s = "a" 输出：[["a"]]`

提示：

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

动态规划 + 回溯算法

求所有的分割方案，凡是求所有方案的题基本上都没有什么优化方案，就是「爆搜」。

问题在于，爆搜什么？显然我们可以爆搜每个回文串的起点。如果有连续的一段是回文串，我们再对剩下连续的一段继续爆搜。

为什么能够直接接着剩下一段继续爆搜？

因为任意的子串最终必然能够分割成若干的回文串（最坏的情况下，每个回文串都是一个字母）。

所以我们每次往下爆搜时，只需要保证自身连续一段是回文串即可。

举个🌰 来感受下我们的爆搜过程，假设有样例 abababa，刚开始我们从起点第一个 a 进行爆搜：

发现 a 是回文串，先将 a 分割出来，再对剩下的 bababa 进行爆搜
发现 aba 是回文串，先将 aba 分割出来，再对剩下的 baba 进行爆搜
发现 ababa 是回文串，先将 ababa 分割出来，再对剩下的 ba 进行爆搜
发现 abababa 是回文串，先将 abababa 分割出来，再对剩下的 `` 进行爆搜

…

然后再对下一个起点（下个字符） b 进行爆搜？

不需要。

因为单个字符本身构成了回文串，所以以 b 为起点，b 之前构成回文串的方案，必然覆盖在我们以第一个字符为起点所展开的爆搜方案内（在这里就是对应了上述的第一步所展开的爆搜方案中）。

因此我们只需要以首个字符为起点，枚举以其开头所有的回文串方案，加入集合，然后对剩下的字符串部分继续爆搜。就能做到以任意字符作为回文串起点进行分割的效果了。

一定要好好理解上面那句话 ~

剩下的问题是，我们如何快速判断连续一段 [i, j] 是否为回文串，因为爆搜的过程每个位置都可以作为分割点，复杂度为 $O(2^n)$ 的。

因此我们不可能每次都使用双指针去线性扫描一遍 [i, j] 判断是否回文。

一个直观的做法是，我们先预处理除所有的 f[i][j]，f[i][j] 代表 [i, j] 这一段是否为回文串。

预处理 f[i][j] 的过程可以用递推去做。

要想 f[i][j] == true ，必须满足以下两个条件：

f[i + 1][j - 1] == true
s[i] == s[j]

由于状态 f[i][j] 依赖于状态 f[i + 1][j - 1]，因此需要我们左端点 i 是从大到小进行遍历；而右端点 j 是从小到大进行遍历。

因此，我们的遍历过程可以整理为：右端点 j 一直往右移动（从小到大），在 j 固定情况下，左端点 i 在 j 在左边开始，一直往左移动（从大到小）

Java 代码：

class Solution {
    public List<List<String>> partition(String s) {
        int n = s.length();
        char[] cs = s.toCharArray();
        // f[i][j] 代表 [i, j] 这一段是否为回文串
        boolean[][] f = new boolean[n][n];
        for (int j = 0; j < n; j++) {
            for (int i = j; i >= 0; i--) {
                // 当 [i, j] 只有一个字符时，必然是回文串
                if (i == j) {
                    f[i][j] = true;
                } else {
                    // 当 [i, j] 长度为 2 时，满足 cs[i] == cs[j] 即回文串
                    if (j - i + 1 == 2) {
                        f[i][j] = cs[i] == cs[j];

                    // 当 [i, j] 长度大于 2 时，满足 (cs[i] == cs[j] && f[i + 1][j - 1]) 即回文串
                    } else {
                        f[i][j] = cs[i] == cs[j] && f[i + 1][j - 1];
                    }
                }
            }
        }
        List<List<String>> ans = new ArrayList<>();
        List<String> cur = new ArrayList<>();
        dfs(s, 0, ans, cur, f);
        return ans;
    }
    /**
     * s: 要搜索的字符串
     * u: 以 s 中的那一位作为回文串分割起点
     * ans: 最终结果集
     * cur: 当前结果集
     * f: 快速判断 [i,j] 是否为回文串
     */
    void dfs(String s, int u, List<List<String>> ans, List<String> cur, boolean[][] f) {
        int n = s.length();
        if (u == n) ans.add(new ArrayList<>(cur));
        for (int i = u; i < n; i++) {
            if (f[u][i]) {
                cur.add(s.substring(u, i + 1));
                dfs(s, i + 1, ans, cur, f);
                cur.remove(cur.size() - 1);
            }
        }
    }
}

C++ 代码：

class Solution {
public:
    vector<vector<string>> partition(string s) {
        int n = s.length();
        vector<vector<string>> ans;
        vector<string> cur;
        vector<vector<bool>> f(n, vector<bool>(n, false));
        for (int j = 0; j < n; j++) {
            for (int i = j; i >= 0; i--) {
                if (i == j) {
                    f[i][j] = true;
                } else if (j - i + 1 == 2) {
                    f[i][j] = s[i] == s[j];
                } else {
                    f[i][j] = s[i] == s[j] && f[i + 1][j - 1];
                }
            }
        }
        dfs(s, 0, ans, cur, f);
        return ans;
    }
    void dfs(string& s, int u, vector<vector<string>>& ans, vector<string>& cur, vector<vector<bool>>& f) {
        int n = s.length();
        if (u == n) ans.push_back(cur);
        for (int i = u; i < n; i++) {
            if (f[u][i]) {
                cur.push_back(s.substr(u, i - u + 1));
                dfs(s, i + 1, ans, cur, f);
                cur.pop_back();
            }
        }
    }
};

Python 代码：

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        def dfs(s: str, u: int, ans: List[List[str]], cur: List[str], f: List[List[bool]]):
            n = len(s)
            if u == n:
                ans.append(cur[:])
            for i in range(u, n):
                if f[u][i]:
                    cur.append(s[u:i + 1])
                    dfs(s, i + 1, ans, cur, f)
                    cur.pop()

        n = len(s)
        ans, cur = [], []
        f = [[False] * n for _ in range(n)]
        for j in range(n):
            for i in range(j, -1, -1):
                if i == j:
                    f[i][j] = True
                elif j - i + 1 == 2:
                    f[i][j] = s[i] == s[j]
                else:
                    f[i][j] = s[i] == s[j] and f[i + 1][j - 1]
        dfs(s, 0, ans, cur, f)
        return ans

TypeScript 代码：

function partition(s: string): string[][] {
    const dfs = function(s: string, u: number, ans: string[][], cur: string[], f: boolean[][]): void {
        const n = s.length;
        if (u == n) ans.push([...cur]);
        for (let i = u; i < n; i++) {
            if (f[u][i]) {
                cur.push(s.substring(u, i + 1));
                dfs(s, i + 1, ans, cur, f);
                cur.pop();
            }
        }
    };
    const n = s.length;
    const ans = [], cur = [];
    const f = Array.from({ length: n }, () => Array(n).fill(false));
    for (let j = 0; j < n; j++) {
        for (let i = j; i >= 0; i--) {
            if (i == j) {
                f[i][j] = true;
            } else if (j - i + 1 === 2) {
                f[i][j] = s[i] == s[j];
            } else {
                f[i][j] = s[i] == s[j] && f[i + 1][j - 1];
            }
        }
    }
    dfs(s, 0, ans, cur, f);
    return ans;
};

时间复杂度：动态规划预处理的复杂度为 $O(n^2)$；爆搜过程中每个字符都可以作为分割点，并且有分割与不分割两种选择，方案数量为 $2^{n - 1}$，每个字符都需要往后检查剩余字符的分割情况，复杂度为 $O(n)$。整体复杂度为 $O(n \times 2^n)$
空间复杂度：动态规划部分的复杂度为 $O(n^2)$；方案数量最多为 $2^{n - 1}$，每个方案都是完整字符串 s 的分割，复杂度为 $O(n)$，整体复杂度为 $O(n \times 2^n)$

总结

对于此类要枚举所有方案的题目，我们都应该先想到「回溯算法」。

「回溯算法」从算法定义上来说，不一定要用 DFS 实现，但通常结合 DFS 来做，难度是最低的。

「回溯算法」根据当前决策有多少种选择，对应了两套模板。

每一次独立的决策只对应选择和不选两种情况：

确定结束回溯过程的 base case
遍历每个位置，对每个位置进行决策（做选择 -> 递归 -> 撤销选择）

void dfs(当前位置, 路径(当前结果), 结果集) {
    if (当前位置 == 结束位置) {
        结果集.add(路径);
        return;
    }
        
    选择当前位置;    
    dfs(下一位置, 路径(当前结果), 结果集);
    撤销选择当前位置;
    dfs(下一位置, 路径(当前结果), 结果集);
}

每一次独立的决策都对应了多种选择（通常对应了每次决策能选择什么，或者每次决策能选择多少个 …）:

确定结束回溯过程的 base case
遍历所有的「选择」
对选择进行决策 (做选择 -> 递归 -> 撤销选择)

void dfs(选择列表, 路径(当前结果), 结果集) {
    if (满足结束条件) {
        结果集.add(路径);
        return;
    }
        
    for (选择 in 选择列表) {
        做选择;
        dfs(路径’, 选择列表, 结果集);
        撤销选择;
    }
}

最后

这是我们「刷穿 LeetCode」系列文章的第 No.131 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

动态规划回溯算法回文串

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

LC 132. 分割回文串 II 上一篇

LC 503. 下一个更大元素 II 下一篇