分割回文串，有点难！

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

创新互联总部坐落于成都市区，致力网站建设服务有成都做网站、网站制作、网络营销策划、网页设计、网站维护、公众号搭建、微信小程序定制开发、软件开发等为企业提供一整套的信息化建设解决方案。创造真正意义上的网站建设，为互联网品牌在互动行销领域创造价值而不懈努力！

分割回文串

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

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

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

示例:

输入: "aab"

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

思路

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

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

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

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

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

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

例如对于字符串abcdef：

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

感受出来了不?

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

分割回文串

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

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

回溯三部曲

  • 递归函数参数

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

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

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

代码如下：

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

分割回文串

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

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

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

所以终止条件代码如下：

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

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

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

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

代码如下：

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

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

判断回文子串

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

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

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

 
 
 
 
    
  
  
  
  
  1. bool isPalindrome(const string& s, int start, int end) {
    2. 
  
  
  
  
  2.     for (int i = start, j = end; i < j; i++, j--) {
    3. 
  
  
  
  
  3.         if (s[i] != s[j]) {
    4. 
  
  
  
  
  4.             return false;
    5. 
  
  
  
  
  5.         }
    6. 
  
  
  
  
  6.     }
    7. 
  
  
  
  
  7.     return true;
    8. 
  
  
  
  
  8. }
    9.

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

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

C++整体代码

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

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

不难写出如下代码：

 
 
 
 
    
  
  
  
  
  1. class Solution {
    2. 
  
  
  
  
  2. private:
    3. 
  
  
  
  
  3.     vector> result;
    4. 
  
  
  
  
  4.     vector path; // 放已经回文的子串
    5. 
  
  
  
  
  5.     void backtracking (const string& s, int startIndex) {
    6. 
  
  
  
  
  6.         // 如果起始位置已经大于s的大小，说明已经找到了一组分割方案了
    7. 
  
  
  
  
  7.         if (startIndex >= s.size()) {
    8. 
  
  
  
  
  8.             result.push_back(path);
    9. 
  
  
  
  
  9.             return;
    10. 
  
  
  
  
  10.         }
    11. 
  
  
  
  
  11.         for (int i = startIndex; i < s.size(); i++) {
    12. 
  
  
  
  
  12.             if (isPalindrome(s, startIndex, i)) {   // 是回文子串
    13. 
  
  
  
  
  13.                 // 获取[startIndex,i]在s中的子串
    14. 
  
  
  
  
  14.                 string str = s.substr(startIndex, i - startIndex + 1);
    15. 
  
  
  
  
  15.                 path.push_back(str);
    16. 
  
  
  
  
  16.             } else {                                // 不是回文，跳过
    17. 
  
  
  
  
  17.                 continue;
    18. 
  
  
  
  
  18.             }
    19. 
  
  
  
  
  19.             backtracking(s, i + 1); // 寻找i+1为起始位置的子串
    20. 
  
  
  
  
  20.             path.pop_back(); // 回溯过程，弹出本次已经填在的子串
    21. 
  
  
  
  
  21.         }
    22. 
  
  
  
  
  22.     }
    23. 
  
  
  
  
  23.     bool isPalindrome(const string& s, int start, int end) {
    24. 
  
  
  
  
  24.         for (int i = start, j = end; i < j; i++, j--) {
    25. 
  
  
  
  
  25.             if (s[i] != s[j]) {
    26. 
  
  
  
  
  26.                 return false;
    27. 
  
  
  
  
  27.             }
    28. 
  
  
  
  
  28.         }
    29. 
  
  
  
  
  29.         return true;
    30. 
  
  
  
  
  30.     }
    31. 
  
  
  
  
  31. public:
    32. 
  
  
  
  
  32.     vector> partition(string s) {
    33. 
  
  
  
  
  33.         result.clear();
    34. 
  
  
  
  
  34.         path.clear();
    35. 
  
  
  
  
  35.         backtracking(s, 0);
    36. 
  
  
  
  
  36.         return result;
    37. 
  
  
  
  
  37.     }
    38. 
  
  
  
  
  38. };
    39.

总结

这道题目在leetcode上是中等，但可以说是hard的题目了，但是代码其实就是按照模板的样子来的。

那么难究竟难在什么地方呢?

我列出如下几个难点：

  • 切割问题可以抽象为组合问题
  • 如何模拟那些切割线
  • 切割问题中递归如何终止
  • 在递归循环中如何截取子串
  • 如何判断回文

我们平时在做难题的时候，总结出来难究竟难在哪里也是一种需要锻炼的能力。

一些同学可能遇到题目比较难，但是不知道题目难在哪里，反正就是很难。其实这样还是思维不够清晰，这种总结的能力需要多接触多锻炼。

本题我相信很多同学主要卡在了第一个难点上：就是不知道如何切割，甚至知道要用回溯法，也不知道如何用。也就是没有体会到按照求组合问题的套路就可以解决切割。

如果意识到这一点，算是重大突破了。接下来就可以对着模板照葫芦画瓢。

但接下来如何模拟切割线，如何终止，如何截取子串，其实都不好想，最后判断回文算是最简单的了。

关于模拟切割线，其实就是index是上一层已经确定了的分割线，i是这一层试图寻找的新分割线

除了这些难点，本题还有细节，例如：切割过的地方不能重复切割所以递归函数需要传入i + 1。

所以本题应该是一个道hard题目了。

可能刷过这道题目的录友都没感受到自己原来克服了这么多难点，就把这道题目AC了，这应该叫做无招胜有招，人码合一，哈哈哈。

本文转载自微信公众号「代码随想录」，可以通过以下二维码关注。转载本文请联系代码随想录公众号。

本文标题：分割回文串，有点难！
文章转载：http://www.shufengxianlan.com/qtweb/news12/504562.html

网站建设、网络推广公司-创新互联，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联

猜你还喜欢下面的内容

自适应网站知识

同城分类信息

温江网站制作　　 　成都定制网站开发　　 　成都网站运营维护　　 　小程序开发　　 　云锦斋建筑　　 　成都网站建设　　 　云主机　　 　响应式网站　　 　成都商城网站制作　　 　雕琢时光茶叶　　 　SSL认证　　 　成都定制网页设计　　 　LED网站设计方案　　 　成都网站制作　　 　成都定制网站建设　　 　广安网站设计　　 　成都添翼二手车　　 　专业网站设计　　 　商城网站建设　　 　成都网站推广