📝 题目描述

题目链接：分割回文串

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

子字符串是字符串中连续的 非空 字符序列。
回文串是向前和向后读都相同的字符串。

示例：

1
2
3
4
5
6
7
8
9
示例 1：

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

示例 2：

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

提示：

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

💡 解题思路

方法一：动态规划 + 回溯

思路：

由于需要求出字符串 ss 的所有分割方案，因此我们考虑使用搜索 + 回溯的方法枚举所有可能的分割方法并进行判断。

假设我们当前搜索到字符串的第 ii 个字符，且 s[0..i−1]s[0..i−1] 位置的所有字符已经被分割成若干个回文串，并且分割结果被放入了答案数组 ansans 中，那么我们就需要枚举下一个回文串的右边界 jj，使得 s[i..j]s[i..j] 是一个回文串。

因此，我们可以从 ii 开始，从小到大依次枚举 jj。对于当前枚举的 jj 值，我们使用双指针的方法判断 s[i..j]s[i..j] 是否为回文串：如果 s[i..j]s[i..j] 是回文串，那么就将其加入答案数组 ansans 中，并以 j+1j+1 作为新的 ii 进行下一层搜索，并在未来的回溯时将 s[i..j]s[i..j] 从 ansans 中移除。

如果我们已经搜索完了字符串的最后一个字符，那么就找到了一种满足要求的分割方法。

动态规划优化：

当我们在判断 s[i..j]s[i..j] 是否为回文串时，常规的方法是使用双指针分别指向 ii 和 jj，每次判断两个指针指向的字符是否相同，直到两个指针相遇。然而这种方法会产生重复计算，例如下面这个例子：

当 s=s=aaba 时，对于前 2 个字符 aa，我们有 2 种分割方法 [aa][aa] 和 [a,a][a,a]，当我们每一次搜索到字符串的第 i=2i=2 个字符 b 时，都需要对于每个 s[i..j]s[i..j] 使用双指针判断其是否为回文串，这就产生了重复计算。

因此，我们可以将字符串 ss 的每个子串 s[i..j]s[i..j] 是否为回文串预处理出来，使用动态规划即可。设 f(i,j)f(i,j) 表示 s[i..j]s[i..j] 是否为回文串，那么有状态转移方程：

f(i,j)={s[i]==s[j],j−i≤2f(i+1,j−1)∧(s[i]==s[j]), otherwise f(i,j) = \begin{cases} s[i] == s[j], & j - i \leq 2 \\ f(i+1,j-1) \land (s[i] == s[j]), & \text{ otherwise } \end{cases}

其中 ∧∧ 表示逻辑与运算。
即 s[i..j]s[i..j] 为回文串，当且仅当：

  • j−i≤2j−i≤2 时，只要 s[i]==s[j]s[i]==s[j]，它就是回文串（例如 “a”, “aa”, “aba”），
  • 首尾字符相同且 s[i+1..j−1]s[i+1..j−1] 为回文串。

预处理完成之后，我们只需要 O(1)O(1) 的时间就可以判断任意 s[i..j]s[i..j] 是否为回文串了。

方法二：动态分割 + 回溯

开始遍历时，我们可以视为前面已经分割好了，我们的起始点 nextstart 是 s[0]，目前已经遍历到了 current = s[0] 的位置。

那么在每个 current 点，我们可以判定从 nextstart 到 current 是否为回文串。

  • 如果是，那么我们可以选择在 current 点切割，然后更新新的 nextstart 为 current + 1；更新新的 current 为 current + 1，继续递归。
  • 如果是，我们可以回溯，选择不在 current 点切割，更新新的 current 为 current + 1，继续递归。
  • 如果不是，我们只能更新新的 current 为 current + 1，继续递归。

终止条件是 nextstart == s.size() 也就是切割完成整个字符串，或者 nextstart == s.size() 越界了依然没有分割。

🔧 代码实现

1、动态规划 + 回溯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution {
private:
    vector<vector<string>> ans;
    vector<string> track;
    vector<vector<int>> dp; // dp[i][j] 记录 s[i..j] 是否为回文串

    void backtrack(const string& s, int startIndex) {
        // 如果起始位置已经到了字符串末尾，说明找到了一组分割方案
        if (startIndex >= s.size()) {
            ans.push_back(track);
            return;
        }

        // 从 startIndex 开始，枚举所有的切割终点 i
        for (int i = startIndex; i < s.size(); i++) {
            // 通过 dp 数组 $O(1)$ 判断是否为回文串
            if (dp[startIndex][i]) {
                // 截取回文子串并加入路径
                track.push_back(s.substr(startIndex, i - startIndex + 1));
                
                // 向下递归，起始位置变为 i + 1
                backtrack(s, i + 1);
                
                // 回溯，撤销选择
                track.pop_back();
            }
        }
    }

public:
    vector<vector<string>> partition(string s) {
        int n = s.size();
        // 1. 动态规划预处理回文串信息
        // 初始化全为 0 (false)
        dp.assign(n, vector<int>(n, 0));
        
        // 注意遍历顺序：i 从大到小，j 从小到大，保证 dp[i+1][j-1] 已经被计算过
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (s[i] == s[j] && (j - i <= 2 || dp[i + 1][j - 1])) {
                    dp[i][j] = 1;
                }
            }
        }

        // 2. 开启回溯
        backtrack(s, 0);
        return ans;
    }
};

2、动态分割 + 回溯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
    bool isPalindrome(string& s, int nextstart, int current) {
        if (nextstart == current) return true;
        while (nextstart <= current) {
            if (s[nextstart] != s[current]) {
                return false;
            }
            nextstart++;
            current--;
        }
        return true;
    }
    void backtrack(vector<vector<string>>& ans, vector<string>& track, string& s, int nextstart, int current) {
        if (nextstart == s.size()) {
            ans.push_back(track);
            return;
        }

        if (current == s.size()) {
            return;
        }

        if (isPalindrome(s, nextstart, current)) {
            track.push_back(s.substr(nextstart, current - nextstart + 1));
            backtrack(ans, track, s, current + 1, current + 1);
            track.pop_back();
        }

        backtrack(ans, track, s, nextstart, current + 1);
    }
    vector<vector<string>> partition(string s) {
        vector<vector<string>> ans;
        vector<string> track;
        backtrack(ans, track, s, 0, 0);
        return ans;
    }
};

📊 复杂度分析

1、动态规划 + 回溯

  • 时间复杂度：O(n⋅2n)O(n⋅2^n)，其中 n 是字符串 s 的长度。在最坏情况下，s 包含 n 个完全相同的字符，因此它的任意一种划分方法都满足要求。而长度为 n 的字符串的划分方案数为 2n−1=O(2n)2^{n−1}=O(2^n)，每一种划分方法需要 O(n)O(n) 的时间求出对应的划分结果并放入答案，因此总时间复杂度为 O(n⋅2n)O(n⋅2^n)。
  • 空间复杂度：O(n2)O(n^2)：除了递归栈和 track 数组的 O(n)O(n) 空间外，还需要额外开辟一个 n×nn×n 的二维数组 dp。

2、动态分割 + 回溯

  • 时间复杂度：O(n⋅2n)O(n⋅2^n)，其中 n 是字符串 s 的长度。在最坏情况下，s 包含 n 个完全相同的字符，因此它的任意一种划分方法都满足要求。而长度为 n 的字符串的划分方案数为 2n−1=O(2n)2^{n−1}=O(2^n)，每一种划分方法需要 O(n)O(n) 的时间求出对应的划分结果并放入答案，因此总时间复杂度为 O(n⋅2n)O(n⋅2^n)。
  • 空间复杂度：O(n)O(n)：仅依赖递归调用栈的最大深度，以及存放当前路径的 track 数组。最大深度为 n。

🎯 总结

  • 核心思想：掌握动态规划的写法。