分割回文串

题意

给定字符串 s，将其分割成若干子串，使每个子串都是回文串。返回所有可能的分割方案。

思路

最直接的思路是枚举所有切分方式，逐一检查每段是否回文：

cpp

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// brute.cpp：小数据暴力解，枚举每段终点只递归回文前缀，与 main.cpp 同序。
#include <bits/stdc++.h>
using namespace std;

string s;
int n;
vector<vector<string>> ans;
vector<string> cur;

bool is_pal(int l, int r) {
    while (l < r) {
        if (s[l] != s[r])
            return false;
        l++;
        r--;
    }
    return true;
}

void dfs(int i) {
    if (i == n) {
        ans.push_back(cur);
        return;
    }
    for (int j = i; j < n; j++) {
        if (is_pal(i, j)) {
            cur.push_back(s.substr(i, j - i + 1));
            dfs(j + 1);
            cur.pop_back();
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> s;
    n = s.size();
    dfs(0);
    for (auto &v : ans) {
        for (auto &x : v)
            cout << x << ' ';
        cout << '\n';
    }
    return 0;
}

brute.cpp 每次枚举 s[i..j] 作为下一段，只有当它是回文时才递归 dfs(j+1)。这种"只递归回文前缀"的剪枝已经排除了大量无效分支。

优化的关键是：将回文判断从 $O(k)$ 降到 $O(1)$ 。预处理 pal[i][j] 表示 s[i..j] 是否回文：pal[i][j] = (s[i]==s[j]) && (j-i<2 || pal[i+1][j-1])，从右下向左上填充。递归时只需查表，不再逐字符比较。

代码

cpp

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#include <bits/stdc++.h>
using namespace std;

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin >> s;
    for (auto &v : Solution().partition(s)) {
        for (auto &x : v)
            cout << x << ' ';
        cout << '\n';
    }
    return 0;
}

python

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#!/usr/bin/env python3
from typing import List


class Solution:
    def partition(self, s: str) -> List[List[str]]:
        n = len(s)
        pal = [[False] * n for _ in range(n)]
        for i in range(n - 1, -1, -1):
            for j in range(i, n):
                pal[i][j] = s[i] == s[j] and (j - i < 2 or pal[i + 1][j - 1])
        ans, cur = [], []

        def dfs(i):
            if i == n:
                ans.append(cur[:])
                return
            for j in range(i, n):
                if pal[i][j]:
                    cur.append(s[i : j + 1])
                    dfs(j + 1)
                    cur.pop()

        dfs(0)
        return ans


def main():
    s = input().strip()
    for v in Solution().partition(s):
        print(*v)


if __name__ == "__main__":
    main()

复杂度

时间复杂度：最坏 $O(n \cdot 2^n)$ ，每个位置切或不切，预处理 $O(n^2)$ 。
空间复杂度： $O(n^2)$ ，回文表。

总结

分割类回溯的核心是"枚举下一段终点，只递归合法前缀"。预处理区间回文表将判断从 $O(k)$ 降到 $O(1)$ ，是经典的"预处理加速回溯"模式。

目录

题意

思路

代码

复杂度

总结