本文最后更新于:2022年4月9日 中午
给定一个字符串 s,将 s 分割成一些子串,使每个子串都是回文串。
返回 s 所有可能的分割方案。
示例:
| 输入: "aab" 输出: [ ["aa","b"], ["a","a","b"] ]
|
Solution
参考 @liuyubobobo 、@liweiwei1419 、代码随想录
思考如何根据这棵递归树编码:
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
| 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; } };
|
题目难点:
- 切割问题可以抽象为组合问题
- 如何模拟那些切割线
- 切割问题中递归如何终止
- 在递归循环中如何截取子串
- 如何判断回文