LeetCode刷题复盘笔记——131. 分割回文串（一文搞懂回溯解决经典的分割回文串问题）

今日主要总结一下，131. 分割回文串

题目：131. 分割回文串

Leetcode题目地址

题目描述：
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

回文串 是正着读和反着读都一样的字符串。

示例 1：

输入：s = “aab”
输出：[[“a”,“a”,“b”],[“aa”,“b”]]
示例 2：

输入：s = “a”
输出：[[“a”]]

提示：

1 <= s.length <= 16
s 仅由小写英文字母组成

本题重难点

这个题目算比较难的，第一眼看这道题主要有以下几个会遇到比较困难的问题：

1. 如何使用回溯？
2. 切割问题可以抽象为什么问题？
3. 如何模拟那些分割线？
4. 分割问题中递归如何终止？
5. 在递归循环中如何截取子串？
6. 如何判断回文？

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

例如对于字符串abcdef：

组合问题：选取一个a之后，在bcdef中再去选取第二个，选取b之后在cdef中在选组第三个…。
切割问题：切割一个a之后，在bcdef中再去切割第二段，切割b之后在cdef中在切割第三段…。
所以切割问题，也可以抽象为一棵树形结构，如图：

递归用来纵向遍历，for循环用来横向遍历，切割线（就是图中的红线）切割到字符串的结尾位置，说明找到了一个切割方法。
此时可以发现，切割问题的回溯搜索的过程和组合问题的回溯搜索的过程是差不多的。

一、正确解法

C++代码

class Solution {
public:
    vector<string> path;
    vector<vector<string>> res;
    bool isPalindrome(const string& s, int start, int end){
        while(start < end){
            if(s[start] == s[end]){
                start++;
                end--;
            }
            else return false;
        }
        return true;
    }
    void backtracing(const string& s, int startIndex){
        if(startIndex >= s.size()){
            res.push_back(path);
            return;
        }
        for(int i = startIndex; i < s.size(); i++){
            if(isPalindrome(s, startIndex, i)){
                string str = s.substr(startIndex, i - startIndex + 1);
                path.push_back(str);
            }
            else continue;
            backtracing(s, i + 1);
            path.pop_back();
        }
        return;
    }
    vector<vector<string>> partition(string s) {
        path.clear();
        res.clear();
        backtracing(s, 0);
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

总结

针对一开始提到的本题重难点可以稍微总结一下：

1. 切割问题可以抽象为组合问题
2. 如何模拟那些切割线——startIndex（之前的文章讲过，表示下一轮递归遍历的起始位置，这个startIndex就是切割线）
3. 切割问题中递归如何终止——从树形结构的图中可以看出：切割线切到了字符串最后面，说明找到了一种切割方法，此时就是本层递归的终止终止条件。
4. 在递归循环中如何截取子串——我们 定义了起始位置startIndex，那么 [startIndex, i] 就是要截取的子串。
5. 如何判断回文——可以使用双指针法，一个指针从前向后，一个指针从后先前，如果前后指针所指向的元素是相等的，就是回文字符串了。

---

欢迎大家关注本人公众号：编程复盘与思考随笔

(关注后可以免费获得本人在csdn发布的资源源码)

公众号主要记录编程和刷题时的总结复盘笔记和心得！并且分享读书、工作、生活中的一些思考感悟！