app设计网站模板,淡蓝色网站,东莞市五金有限公司 寮步 技术支持 网站建设,有做喜糖的网站吗131. 分割回文串 - 力扣#xff08;LeetCode#xff09;
给你一个字符串 s#xff0c;请你将 s 分割成一些子串#xff0c;使每个子串都是 回文串 。返回 s 所有可能的分割方案。回文串 是正着读和反着读都一样的字符串
示例 1#xff1a;
输入#xff1a;s aa…131. 分割回文串 - 力扣LeetCode
给你一个字符串 s请你将 s 分割成一些子串使每个子串都是 回文串 。返回 s 所有可能的分割方案。回文串 是正着读和反着读都一样的字符串
示例 1
输入s aab
输出[[a,a,b],[aa,b]]
示例 2
输入s a
输出[[a]] 思路和分析
切割问题有不同的切割方式判断回文
代码随想录的Carl老师说“切割问题类似组合问题”这段文字来自代码随想录--分割回文串 对于字符串abcdef 组合问题选取一个a之后在bcdef中再去选取第二个选取b之后在cdef中再选取第三个.....切割问题切割一个a之后在bcdef中再去切割第二段切割b之后在cdef中再切割第三段..... 回溯三部曲:
1).确定回溯函数参数
path 存放切割后回文的子串result 保存 path,作为结果集startIndex 来控制for循环的起始位置表示下一轮递归遍历的起始位置还用来表示这条切割线.(切割过的地方不能重复切割和组合问题也是保持一致的【这句话来自代码随想录】)
vectorvectorstring result;
vectorstring path; // 放已经回文的子串
void backtracking (const string s, int startIndex) // startIndex 就用来表示这条切割线
2).递归的终止条件
如果切割线切到了字符串最后面表示找了一种切割方法此时终止本层递归也就是出现这种情况 startIndex s.size()收集结果后直接return
void backtracking (const string s, int startIndex) {// 如果起始位置已经大于s的大小说明已经找到了一组分割方案了if (startIndex s.size()) {result.push_back(path);return;}
}
3).单层搜索的逻辑
问题(O_O)?思考在递归循环中如何截取子串呢
[startIndex,i]左闭右闭表示子串的起始位置和终止位置有截取区间就可以截取子串。substr(startIndex, i - startIndex 1);
问题(O_O)?思考如何判断所截取子串是否为回文子串呢
判断是否为回文子串:isPalindrome(s, startIndex, i)用双指针法如果是回文就加入在vectorstring path中path 用来记录切割过的回文子串
for (int i startIndex; i s.size(); i) {if (isPalindrome(s, startIndex, i)) { // 是回文子串// 获取[startIndex,i]在s中的子串string str s.substr(startIndex, i - startIndex 1);path.push_back(str);} else { // 如果不是则直接跳过continue;}backtracking(s, i 1); // 寻找i1为起始位置的子串path.pop_back(); // 回溯过程弹出本次已经添加的子串
}
注意切割过的位置不能重复切割应传入下一层的起始位置为 i 1即
backtracking(s, i 1); 1判断是否为回文子串
bool isPalindrome(const string s, int start, int end) {for (int i start, j end; i j; i, j--) {if (s[i] ! s[j]) {return false;}}return true;}
bool isPalindrome(string s) {int left 0,right s.size()-1;while(leftright) {if (s[left] ! s[right]) return false;left;right--;}return true;
} 2C代码
class Solution {
private:vectorvectorstring result;vectorstring path; // 放已经回文的子串void backtracking (const string s, int startIndex) {// 如果起始位置已经大于s的大小说明已经找到了一组分割方案了if (startIndex s.size()) {result.push_back(path);return;}for (int i startIndex; i s.size(); i) {if (isPalindrome(s, startIndex, i)) { // 是回文子串// 获取[startIndex,i]在s中的子串string str s.substr(startIndex, i - startIndex 1);path.push_back(str);} else { // 不是回文跳过continue;}backtracking(s, i 1); // 寻找i1为起始位置的子串path.pop_back(); // 回溯过程弹出本次已经添加的子串}}bool isPalindrome(const string s, int start, int end) {for (int i start, j end; i j; i, j--) {if (s[i] ! s[j]) {return false;}}return true;}
public:vectorvectorstring partition(string s) {backtracking(s, 0);return result;}
};
时间复杂度: O(n * 2^n)空间复杂度: O(n^2)
class Solution {
public:vectorvectorstring result;vectorstring path; // 放已经回文的子串bool isPalindrome(string s) {int left 0,right s.size()-1;while(leftright) {if (s[left] ! s[right]) return false;left;right--;}return true;}void backtracking(string s,int startIndex) {// 如果起始位置已经大于s的大小说明已经找到了一组分割方案了if(startIndex s.size()) {result.push_back(path);return;}for(int istartIndex;is.size();i) {// 获取[startIndex,i]在s中的子串string subStr s.substr(startIndex,i-startIndex1);if(isPalindrome(subStr)) path.push_back(subStr);// 是回文子串else continue;// 不是回文跳过backtracking(s, i 1); // 寻找i1为起始位置的子串path.pop_back(); // 回溯过程弹出本次已经添加的子串}}vectorvectorstring partition(string s) {backtracking(s, 0);return result;}
}; 参考和推荐文章、视频带你学透回溯算法-分割回文串对应力扣题目131.分割回文串| 回溯法精讲_哔哩哔哩_bilibilihttps://www.bilibili.com/video/BV1c54y1e7k6/?p67spm_id_frompageDriver代码随想录 (programmercarl.com)https://www.programmercarl.com/0131.%E5%88%86%E5%89%B2%E5%9B%9E%E6%96%87%E4%B8%B2.html#%E4%BC%98%E5%8C%96
