C++ 实现字符串分割为回文串的方案

思路：

回文串问题通常可以使用动态规划来解决。先预处理出一个二维数组 dp[i][j] 表示字符串 s 中从 i 到 j 的子串是否为回文串，然后利用回溯算法枚举所有可能的分割方案。

具体来说，从字符串 s 的第一个字符开始，依次将所有可能的分割点作为回文串的右边界，然后判断左边的子串是否为回文串，如果是，就递归地处理右边的子串，直到处理到最后一个字符为止。如果右边的子串处理完毕，就回溯到上一个分割点，继续枚举下一个分割点，直到枚举完所有可能的分割点为止。

代码：

#include <iostream>
#include <vector>
#include <string>

using namespace std;

vector<vector<string>> partition(string s) {
    int n = s.length();
    vector<vector<string>> result;
    vector<string> current;
    vector<vector<bool>> dp(n, vector<bool>(n, false));

    // 预处理回文串
    for (int i = n - 1; i >= 0; i--) {
        for (int j = i; j < n; j++) {
            if (i == j) {
                dp[i][j] = true;
            } else if (s[i] == s[j] && (j - i == 1 || dp[i + 1][j - 1])) {
                dp[i][j] = true;
            }
        }
    }

    // 回溯算法
    function backtrack(int start) {
        if (start == n) {
            result.push_back(current);
            return;
        }

        for (int i = start; i < n; i++) {
            if (dp[start][i]) {
                current.push_back(s.substr(start, i - start + 1));
                backtrack(i + 1);
                current.pop_back();
            }
        }
    }

    backtrack(0);
    return result;
}

int main() {
    string s = "aabaa";
    vector<vector<string>> partitions = partition(s);

    for (auto& partition : partitions) {
        for (auto& part : partition) {
            cout << part << " ";
        }
        cout << endl;
    }

    return 0;
}

输出：

a a b a a
a aba a
aa ba a