企业官网建设流程全解析

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

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

示例: 输入: "aab" 输出: [ ["aa","b"], ["a","a","b"] ]

难点

本题的难点在于

1. 怎么理解或者实现分割这个概念。
2. 怎么分割的字符串怎么定义。

分割这个问题类似于组合问题，定义一个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; // 程序正常退出 }