河北手机版建站系统开发,通许网站建设,常州 网站制作,没有网站域名备案信息回溯解法思路#xff1a;
1.先声明一个集合来接受全部的回文子串组合#xff0c;在声明一个集合来接收单个回文子串的组合。
2.写一个回溯函数#xff0c;里面有终止条件和遍历全部组合的for循环来进行遍历全部的组合#xff0c;终止条件为开始索引等于字符串的长度时
1.先声明一个集合来接受全部的回文子串组合在声明一个集合来接收单个回文子串的组合。
2.写一个回溯函数里面有终止条件和遍历全部组合的for循环来进行遍历全部的组合终止条件为开始索引等于字符串的长度时表示遍历完了整个字符串li2加入到li1中去。在遍历for循环中要回溯操作同时要检查分割段是否为回文子串如果不是回文子串就跳过本次循环。 要写一个检查回文子串的函数其中用双指针来检查这个分割段是否是回文子串。
class Solution {//接收全部的回文子串ListListString li1new ArrayList();//接收单个回文子串ListString li2new ArrayList();public ListListString partition(String s) {//调用回溯函数huisu(s,0);return li1;}//回溯函数public void huisu(String s,int startIndex){//判断分割到了字符串的末尾if(startIndexs.length()){li1.add(new ArrayList(li2));return;}//暴力的遍历全部组合for(int jstartIndex;js.length();j){//如果是回文子串则记录if(huiwen(s,startIndex,j)){//进行分割的字符操作String st s.substring(startIndex, j 1);li2.add(st);}else {//不是回文子串跳过这次循环continue;}//调用方法进行递归。huisu(s,j1);//得到回文串之后回溯li2.removeLast();}}//回文函数public boolean huiwen(String s,int startIndex,int j){//遍历用双指针的方法来检查字符串是否是回文子串while(startIndexj){if(s.charAt(startIndex)!s.charAt(j)){return false;}startIndex;j--;}return true;}
}
