Leetcode 131.分割回文串 2021.03.07

Leetcode 131.分割回文串 2021.03.07

三月 07, 2021

131.分割回文串

  • 难度：中等

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

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

示例

输入: “aab”
输出:
[
[“aa”,”b”],
[“a”,”a”,”b”]
]

思路

  • 回溯法+双指针
    1. 双指针检测字符串是否为回文
    2. 设置回溯的出口为字符串长度为0的时候，在返回前，我们将遍历到最深处所保存的字符串数组保存到res数组中
    3. 每一次我们都是从头截取n个字符的子串(其中1<=n<字符串的长度)
    4. 并判断截取的子串是否是回文
      1. 是回文则将当前截取子串放入纵向路径的字符串数组中，并查找子串的子串，直至子串长度为0时返回，返回回来后需要把当前子串从纵向路径的字符串数组中pop掉
      2. 不是回文则直接跳过

代码实现

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
38
39
//回溯法+双指针
class Solution {
public:
    vector<vector<string>> res;//所有纵向路径的字符串数组的数组
    vector<string> path;//纵向路径的字符串数组
	
    //判断字符串是否为回文字符串
    bool isPal(string s){
        int l = 0;
        int r = s.length()-1;
        while(l<r){
            if(s[l] != s[r]) return false;
            l++;
            r--;
        }
        return true;
    }

    void dfs(string s){
        if(s.length() == 0) {
            res.push_back(path);
            return;
        }

        for(int i = 1;i<=s.length();i++){
            string newS = s.substr(0,i);
            if(isPal(newS)){
                path.push_back(newS);
                dfs(s.substr(i));
                path.pop_back();
            }
        }
    }

    vector<vector<string>> partition(string s) {
        dfs(s);
        return res;
    }
};
  1. 1. 131.分割回文串
  2. 2. 示例
  3. 3. 思路
  4. 4. 代码实现