131 分割回文串

本文最后更新于:2022年4月9日 中午

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

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

示例:

1
2
3
4
5
6
输入: "aab"
输出:
[
["aa","b"],
["a","a","b"]
]

Solution

参考 @liuyubobobo@liweiwei1419代码随想录

image.png

思考如何根据这棵递归树编码:

1、每一个结点表示剩余没有扫描到的字符串,产生分支是截取了剩余字符串的前缀;

2、产生前缀字符串的时候,判断前缀字符串是否是回文。

  • 如果前缀字符串是回文,则可以产生分支和结点;
  • 如果前缀字符串不是回文,则不产生分支和结点,这一步是剪枝操作。

3、在叶子结点是空字符串的时候结算

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
// @lc code=start
class Solution {
private:
vector<vector<string>> res;

void dfs(const string& s, int l, vector<string>& cur){
if(l==s.size()){
res.push_back(cur);
return;
}

for(int r=l; r<s.size(); ++r){
if(ispalindrome(s, l, r)){
cur.push_back(s.substr(l, r-l+1));
dfs(s, r+1, cur);
cur.pop_back();
}
}
}

bool ispalindrome(const string& s, int l, int r){
while(l<=r){
if(s[l] != s[r])
return false;
l++, r--;
}
return true;
}

public:
vector<vector<string>> partition(string s) {
vector<string> cur;
dfs(s, 0, cur);
return res;
}
};
// @lc code=end

题目难点:

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

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!