给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
返回 s 所有可能的分割方案。
示例: 输入: "aab" 输出: [ ["aa","b"], ["a","a","b"] ]
难点
本题的难点在于
- 怎么理解或者实现分割这个概念。
- 怎么分割的字符串怎么定义。
分割这个问题类似于组合问题，定义一个startIndex，startIndex指向那个字符就是分割的位置。
for（int i = startIndex; i < s.size(); i ++), 在对字符串进行横向遍历的时候，statrIndex 到 i 的长度不就是分割字符串。
思路
定义参数
vector<vector<string>> result; vector<string> path; // 核心的回溯函数 // s: 输入的原始字符串 // startIndex: 当前遍历的起始位置 void backtracking(const string& s, int startIndex)递归结束条件
当分割到最后一个字符时，说明已经分割完毕，并且一定有满足条件的path，因为每个每个单个字母一定是回文串。
if(startIndex == s.size()){ // 将当前构造的分割方案 (path) 添加到最终结果 (result) 中 result.push_back(path); return; }单层递归逻辑
首先判断分割的字符串是否为回文串，如果是，则压入path。如果不是则跳过，继续考察更长的子串。
当考察到回文串的时候，才会继续向下递归。
// 单层搜索逻辑：从 startIndex 开始，向后遍历字符串 for(int i = startIndex; i < s.size(); i ++){ // 判断从 startIndex 到 i 的子串是否是回文串 if(isPalindrome(s, startIndex, i)){ // 如果是回文串，将其加入到当前路径 (path) 中 // s.substr(startIndex, i - startIndex + 1) 截取了从 startIndex 开始，长度为 i - startIndex + 1 的子串 path.push_back(s.substr(startIndex, i - startIndex + 1)); }else{ // 如果不是回文串，则跳过，继续考察更长的子串 continue; } // 递归：进入下一层决策，起始位置变为 i + 1 backtracking(s, i + 1); // 回溯：撤销当前层的选择，将刚刚加入的子串弹出，以便探索其他可能性 path.pop_back(); }代码
#include<iostream> #include<vector> using namespace std; // 解题的核心类 class Solution { private: vector<vector<string>> result; vector<string> path; // 核心的回溯函数 // s: 输入的原始字符串 // startIndex: 当前遍历的起始位置 void backtracking(const string& s, int startIndex){ // 基本情况（终止条件）：如果起始位置已经等于字符串长度， // 说明我们已经找到了一个完整的分割方案 if(startIndex == s.size()){ // 将当前构造的分割方案 (path) 添加到最终结果 (result) 中 result.push_back(path); return; } // 单层搜索逻辑：从 startIndex 开始，向后遍历字符串 for(int i = startIndex; i < s.size(); i ++){ // 判断从 startIndex 到 i 的子串是否是回文串 if(isPalindrome(s, startIndex, i)){ // 如果是回文串，将其加入到当前路径 (path) 中 // s.substr(startIndex, i - startIndex + 1) 截取了从 startIndex 开始，长度为 i - startIndex + 1 的子串 path.push_back(s.substr(startIndex, i - startIndex + 1)); }else{ // 如果不是回文串，则跳过，继续考察更长的子串 continue; } // 递归：进入下一层决策，起始位置变为 i + 1 backtracking(s, i + 1); // 回溯：撤销当前层的选择，将刚刚加入的子串弹出，以便探索其他可能性 path.pop_back(); } } bool isPalindrome(const string& s, int i, int j){ while(i <= j){ if(s[i] != s[j]){ return false; }else{ i ++; j --; } } return true; } public: vector<vector<string>> partition(string s) { result.clear(); path.clear(); backtracking(s, 0); return result; } }; int main(){ Solution S; string s = "abcd"; vector<vector<string>> result = S.partition(s); for(auto row : result){ for(auto cols : row){ cout << cols << " "; // 打印子串 } cout << endl; // 每打印完一种方案后换行 } return 0; // 程序正常退出 }
