您现在的位置是：亿华云 > 域名

分割回文串，有点难！

亿华云2025-10-03 18:24:30【域名】7人已围观

简介切割问题其实是一种组合问题!分割回文串力扣题目链接：https://leetcode-cn.com/problems/palindrome-partitioning/给定一个字符串 s，将 s 分割成

切割问题其实是有点难一种组合问题!

分割回文串

力扣题目链接：https://leetcode-cn.com/problems/palindrome-partitioning/

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

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

示例:

输入: "aab"

输出: [ ["aa",分割"b"], ["a","a","b"] ]

思路

本题这涉及到两个关键问题：

切割问题，有不同的回文切割方式判断回文

相信这里不同的切割方式可以搞懵很多同学了。

这种题目，有点难想用for循环暴力解法，分割可能都不那么容易写出来，回文所以要换一种暴力的有点难方式，就是分割回溯。

一些同学可能想不清楚回溯究竟是回文如何切割字符串呢?

我们来分析一下切割，其实切割问题类似组合问题。有点难

例如对于字符串abcdef：

组合问题：选取一个a之后，分割在bcdef中再去选取第二个，回文选取b之后在cdef中在选组第三个.....。切割问题：切割一个a之后，在bcdef中再去切割第二段，切割b之后在cdef中在切割第三段.....。

感受出来了不?

所以切割问题，也可以抽象为一颗树形结构，如图：

分割回文串

递归用来纵向遍历，for循环用来横向遍历，切割线(就是图中的红线)切割到字符串的云服务器结尾位置，说明找到了一个切割方法。

此时可以发现，切割问题的回溯搜索的过程和组合问题的回溯搜索的过程是差不多的。

回溯三部曲

递归函数参数

全局变量数组path存放切割后回文的子串，二维数组result存放结果集。(这两个参数可以放到函数参数里)

本题递归函数参数还需要startIndex，因为切割过的地方，不能重复切割，和组合问题也是保持一致的。

在39. 组合总和中我们深入探讨了组合问题什么时候需要startIndex，什么时候不需要startIndex。

代码如下：

vector<vector<string>> result; vector<string> path; // 放已经回文的子串 void backtracking (const string& s, int startIndex) { 递归函数终止条件

分割回文串

从树形结构的图中可以看出：切割线切到了字符串最后面，说明找到了一种切割方法，此时就是本层递归的终止终止条件。

那么在代码里什么是切割线呢?

在处理组合问题的时候，递归参数需要传入startIndex，云南idc服务商表示下一轮递归遍历的起始位置，这个startIndex就是切割线。

所以终止条件代码如下：

void backtracking (const string& s, int startIndex) { // 如果起始位置已经大于s的大小，说明已经找到了一组分割方案了 if (startIndex >= s.size()) { result.push_back(path); return; } } 单层搜索的逻辑

来看看在递归循环，中如何截取子串呢?

在for (int i = startIndex; i < s.size(); i++)循环中，我们定义了起始位置startIndex，那么 [startIndex, i] 就是要截取的子串。

首先判断这个子串是不是回文，如果是回文，就加入在vector path中，path用来记录切割过的回文子串。

代码如下：

for (int i = startIndex; i < s.size(); i++) { if (isPalindrome(s, startIndex, i)) { // 是回文子串 // 获取[startIndex,i]在s中的子串 string str = s.substr(startIndex, i - startIndex + 1); path.push_back(str); } else { // 如果不是则直接跳过 continue; } backtracking(s, i + 1); // 寻找i+1为起始位置的子串 path.pop_back(); // 回溯过程，弹出本次已经填在的子串 }

注意切割过的位置，不能重复切割，所以，backtracking(s, i + 1); 传入下一层的起始位置为i + 1。网站模板

判断回文子串

最后我们看一下回文子串要如何判断了，判断一个字符串是否是回文。

可以使用双指针法，一个指针从前向后，一个指针从后先前，如果前后指针所指向的元素是相等的，就是回文字符串了。

那么判断回文的C++代码如下：

bool isPalindrome(const string& s, int start, int end) { for (int i = start, j = end; i < j; i++, j--) { if (s[i] != s[j]) { return false; } } return true; }

如果大家对双指针法有生疏了，传送门：双指针法：总结篇!

此时关键代码已经讲解完毕，整体代码如下(详细注释了)

C++整体代码

根据Carl给出的回溯算法模板：

void backtracking(参数) { if (终止条件) { 存放结果; return; } for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) { 处理节点; backtracking(路径，选择列表); // 递归回溯，撤销处理结果 } }

不难写出如下代码：

class Solution { private: vector<vector<string>> result; vector<string> path; // 放已经回文的子串 void backtracking (const string& s, int startIndex) { // 如果起始位置已经大于s的大小，说明已经找到了一组分割方案了 if (startIndex >= s.size()) { result.push_back(path); return; } for (int i = startIndex; i < s.size(); i++) { if (isPalindrome(s, startIndex, i)) { // 是回文子串 // 获取[startIndex,i]在s中的子串 string str = s.substr(startIndex, i - startIndex + 1); path.push_back(str); } else { // 不是回文，跳过 continue; } backtracking(s, i + 1); // 寻找i+1为起始位置的子串 path.pop_back(); // 回溯过程，弹出本次已经填在的子串 } } bool isPalindrome(const string& s, int start, int end) { for (int i = start, j = end; i < j; i++, j--) { if (s[i] != s[j]) { return false; } } return true; } public: vector<vector<string>> partition(string s) { result.clear(); path.clear(); backtracking(s, 0); return result; } };