网站需求分析模板,徐州vi设计公司,网站开发自学时间,python做网站 教育131. 分割回文串
给你一个字符串 s#xff0c;请你将 s 分割成一些子串#xff0c;使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。 示例 1#xff1a;
输入#xff1a;s aab
输出#xff1a;[[a请你将 s 分割成一些子串使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。 示例 1
输入s aab
输出[[a,a,b],[aa,b]]示例 2
输入s a
输出[[a]]提示
1 s.length 16s 仅由小写英文字母组成 思路
本题这涉及到两个关键问题
切割问题有不同的切割方式判断回文
相信这里不同的切割方式可以搞懵很多同学了。
这种题目想用for循环暴力解法可能都不那么容易写出来所以要换一种暴力的方式就是回溯。
一些同学可能想不清楚 回溯究竟是如何切割字符串呢
我们来分析一下切割其实切割问题类似组合问题。
例如对于字符串abcdef
组合问题选取一个a之后在bcdef中再去选取第二个选取b之后在cdef中再选取第三个.....。切割问题切割一个a之后在bcdef中再去切割第二段切割b之后在cdef中再切割第三段.....。
感受出来了不
所以切割问题也可以抽象为一棵树形结构如图 递归用来纵向遍历for循环用来横向遍历切割线就是图中的红线切割到字符串的结尾位置说明找到了一个切割方法。
此时可以发现切割问题的回溯搜索的过程和组合问题的回溯搜索的过程是差不多的。
#回溯三部曲
递归函数参数
全局变量数组path存放切割后回文的子串二维数组result存放结果集。 这两个参数可以放到函数参数里
本题递归函数参数还需要startIndex因为切割过的地方不能重复切割和组合问题也是保持一致的。
在回溯算法求组合总和二 (opens new window)中我们深入探讨了组合问题什么时候需要startIndex什么时候不需要startIndex。
代码如下
vectorvectorstring result;
vectorstring path; // 放已经回文的子串
void backtracking (const string s, int startIndex) {递归函数终止条件 从树形结构的图中可以看出切割线切到了字符串最后面说明找到了一种切割方法此时就是本层递归的终止条件。
那么在代码里什么是切割线呢
在处理组合问题的时候递归参数需要传入startIndex表示下一轮递归遍历的起始位置这个startIndex就是切割线。
所以终止条件代码如下
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)循环中我们 定义了起始位置startIndex那么 [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(); // 回溯过程弹出本次已经添加的子串
}注意切割过的位置不能重复切割所以backtracking(s, i 1); 传入下一层的起始位置为i 1。
#判断回文子串
最后我们看一下回文子串要如何判断了判断一个字符串是否是回文。
可以使用双指针法一个指针从前向后一个指针从后向前如果前后指针所指向的元素是相等的就是回文字符串了。
那么判断回文的C代码如下 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;}如果大家对双指针法有生疏了传送门双指针法总结篇(opens new window)
此时关键代码已经讲解完毕整体代码如下详细注释了
根据Carl给出的回溯算法模板
void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择本层集合中元素树中节点孩子的数量就是集合的大小) {处理节点;backtracking(路径选择列表); // 递归回溯撤销处理结果}
} 不难写出如下代码
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) {result.clear();path.clear();backtracking(s, 0);return result;}
};时间复杂度: O(n * 2^n)空间复杂度: O(n^2)
#优化
上面的代码还存在一定的优化空间, 在于如何更高效的计算一个子字符串是否是回文字串。上述代码isPalindrome函数运用双指针的方法来判定对于一个字符串s, 给定起始下标和终止下标, 截取出的子字符串是否是回文字串。但是其中有一定的重复计算存在:
例如给定字符串abcde, 在已知bcd不是回文字串时, 不再需要去双指针操作abcde而可以直接判定它一定不是回文字串。
具体来说, 给定一个字符串s, 长度为n, 它成为回文字串的充分必要条件是s[0] s[n-1]且s[1:n-1]是回文字串。
大家如果熟悉动态规划这种算法的话, 我们可以高效地事先一次性计算出, 针对一个字符串s, 它的任何子串是否是回文字串, 然后在我们的回溯函数中直接查询即可, 省去了双指针移动判定这一步骤.
具体参考代码如下:
class Solution {
private:vectorvectorstring result;vectorstring path; // 放已经回文的子串vectorvectorbool isPalindrome; // 放事先计算好的是否回文子串的结果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[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(); // 回溯过程弹出本次已经添加的子串}}void computePalindrome(const string s) {// isPalindrome[i][j] 代表 s[i:j](双边包括)是否是回文字串 isPalindrome.resize(s.size(), vectorbool(s.size(), false)); // 根据字符串s, 刷新布尔矩阵的大小for (int i s.size() - 1; i 0; i--) { // 需要倒序计算, 保证在i行时, i1行已经计算好了for (int j i; j s.size(); j) {if (j i) {isPalindrome[i][j] true;}else if (j - i 1) {isPalindrome[i][j] (s[i] s[j]);}else {isPalindrome[i][j] (s[i] s[j] isPalindrome[i1][j-1]);}}}}
public:vectorvectorstring partition(string s) {result.clear();path.clear();computePalindrome(s);backtracking(s, 0);return result;}
}; #总结
这道题目在leetcode上是中等但可以说是hard的题目了但是代码其实就是按照模板的样子来的。
那么难究竟难在什么地方呢
我列出如下几个难点
切割问题可以抽象为组合问题如何模拟那些切割线切割问题中递归如何终止在递归循环中如何截取子串如何判断回文
我们平时在做难题的时候总结出来难究竟难在哪里也是一种需要锻炼的能力。
一些同学可能遇到题目比较难但是不知道题目难在哪里反正就是很难。其实这样还是思维不够清晰这种总结的能力需要多接触多锻炼。
本题我相信很多同学主要卡在了第一个难点上就是不知道如何切割甚至知道要用回溯法也不知道如何用。也就是没有体会到按照求组合问题的套路就可以解决切割。
如果意识到这一点算是重大突破了。接下来就可以对着模板照葫芦画瓢。
但接下来如何模拟切割线如何终止如何截取子串其实都不好想最后判断回文算是最简单的了。
关于模拟切割线其实就是index是上一层已经确定了的分割线i是这一层试图寻找的新分割线
除了这些难点本题还有细节例如切割过的地方不能重复切割所以递归函数需要传入i 1。
所以本题应该是一道hard题目了。
可能刷过这道题目的录友都没感受到自己原来克服了这么多难点就把这道题目AC了这应该叫做无招胜有招人码合一。
