商洛市住房和城乡建设局网站,苏州高级网站建设,重庆网络seo公司,公司的网站怎么运营目录题目思路回溯题目来源 131. 分割回文串
题目思路
切割问题类似组合问题。 例如对于字符串abcdef#xff1a;
组合问题#xff1a;选取一个a之后#xff0c;在bcdef中再去选取第二个#xff0c;选取b之后在cdef中再选取第三个…。切割问题#xff1a;切割一个a之后
组合问题选取一个a之后在bcdef中再去选取第二个选取b之后在cdef中再选取第三个…。切割问题切割一个a之后在bcdef中再去切割第二段切割b之后在cdef中再切割第三段…。
抽象为一棵树形结构 递归用来纵向遍历for循环用来横向遍历切割线就是图中的红线切割到字符串的结尾位置说明找到了一个切割方法。
回溯
1.递归函数参数
全局变量数组path存放切割后回文的子串二维数组result存放结果集。 这两个参数可以放到函数参数里 本题递归函数参数还需要startIndex因为切割过的地方不能重复切割和组合问题也是保持一致的。 ArrayListListString result new ArrayList();ArrayListString path new ArrayList();void backTracking(String s,int startIndex)2.递归函数终止条件
从树形结构的图中可以看出切割线切到了字符串最后面说明找到了一种切割方法此时就是本层递归的终止条件。 那么在代码里什么是切割线呢 在处理组合问题的时候递归参数需要传入startIndex表示下一轮递归遍历的起始位置这个startIndex就是切割线。 终止条件代码如下 if(startIndex s.length()){// 如果起始位置已经大于s的大小说明已经找到了一组分割方案了result.add(new ArrayList(path));return;}3.单层搜索的逻辑
来看看在递归循环中如何截取子串呢 在for (int i startIndex; i s.length(); i)循环中我们 定义了起始位置startIndex那么 [startIndex, i] 就是要截取的子串。
首先判断这个子串是不是回文如果是回文就加入在path中path用来记录切割过的回文子串。 for(int i startIndex;is.length();i){//如果是回文子串则记录if(isPalindrome(s,startIndex,i)){String str s.substring(startIndex,i1);path.add(str);}else{continue;}//起始位置后移保证不重复backTracking(s,i1);path.remove(path.size()-1);}注意切割过的位置不能重复切割所以backtracking(s, i 1); 传入下一层的起始位置为i 1。
判断回文子串
可以使用双指针法一个指针从前向后一个指针从后向前如果前后指针所指向的元素是相等的就是回文字符串了。 private boolean isPalindrome(String s,int start,int end){for(int istart,jend;ij;i,j--){if(s.charAt(i) ! s.charAt(j)){return false;}}return true;}整体代码
class Solution {ArrayListListString result new ArrayList();ArrayListString path new ArrayList();public ListListString partition(String s) {if(s null || s.length() 1){return result;}backTracking(s,0);return result;}public void backTracking(String s,int startIndex){// 如果起始位置已经大于s的大小说明已经找到了一组分割方案了if(startIndex s.length()){result.add(new ArrayList(path));return;}for(int i startIndex;is.length();i){//如果是回文子串则记录if(isPalindrome(s,startIndex,i)){String str s.substring(startIndex,i1);path.add(str);}else{continue;}//起始位置后移保证不重复backTracking(s,i1);path.remove(path.size()-1);}}private boolean isPalindrome(String s,int start,int end){for(int istart,jend;ij;i,j--){if(s.charAt(i) ! s.charAt(j)){return false;}}return true;}
}
