(回溯) LeetCode 131. 分割回文串

原题链接

一. 标题形貌

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

1. <strong>输入：</strong>s = "aab"
2. <strong>输出：</strong>[["a","a","b"],["aa","b"]]

复制代码

示例 2：

1. <strong>输入：</strong>s = "a"
2. <strong>输出：</strong>[["a"]]

复制代码

提示：

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

二. 解题思路

首先得明确什么是回文串，回文串就是能够对称的字符串，照旧老样子。
1. 明确递归参数：字符串s 和当前路径的出发点 startindex 。
2. 确定递归的制止条件：当startindex 的巨细凌驾字符串的长度的时候制止，证明已经切割到了字符串的最后，直接将path 路径添加到结果数组res 中即可，这里小同伴可能要问了，你这还没有判定是不是回文串，对，因为我在背面的单层递归中做了限定，只有回文子串才能进path 数组。所以这里的path 数组中一定是回文子串。
3. 单层递归逻辑：相信做了这么多的标题了，一定知道怎么写吧，只必要加一条判定是不是回文子串的限定条件即可，如果是将其加入到path 数组中进行递归即可，如果不是直接continue；最后做好回溯即可。
话不多说！！！上代码！！
三. 代码

1. class Solution {
2. public:
3.     vector<vector<string>> res;
4.     vector<string> path;
5.     bool isPalindrome(string s, int l, int r){        // 判断是不是回文子串
6.         for(int i = l, j = r; i <= j; i++, j--){
7.             if(s[i] != s[j]) return false;
8.         }
9.         return true;
10.     }
11.     void back(string s, int startindex){
12.         if(startindex >= s.size()){
13.             res.push_back(path);
14.             return;
15.         }
16.         for(int i = startindex; i < s.size(); i++){
17.             if(isPalindrome(s, startindex, i)){
18.                 string str = s.substr(startindex, i - startindex + 1);
19.                 path.push_back(str);
20.                 back(s, i + 1);
21.                 path.pop_back();    // 回溯
22.             }
23.         }
24.     }
25.     vector<vector<string>> partition(string s) {
26.         back(s, 0);
27.         return res;
28.     }
29. };

复制代码

四. 总结

如果你将前面的标题做了训练的话相信这类标题已经非常简单了吧！！！继续加油！！！
时间复杂度：O(n * 2^n)
空间复杂度：O(n^2)
喜好的话给个关注吧！！


免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。