开发高端网站开发,零基础网站建设视频教程,如何一键打开多个wordpress,微分销商城开发分割回文串
描述 :
给你一个字符串 s#xff0c;请你将 s 分割成一些子串#xff0c;使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
题目 :
LeetCode 131.分割回文串 :
131. 分割回文串
分析 : 字符串如何判断回文本…分割回文串
描述 :
给你一个字符串 s请你将 s 分割成一些子串使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
题目 :
LeetCode 131.分割回文串 :
131. 分割回文串
分析 : 字符串如何判断回文本身就是一个道算法题本题在其之上还要再解决一个问题: 如何切割? 如果暴力切割是非常困难的如果从回溯的角度来思考就清晰很多: 我们说回溯本身仍然会进行枚举这里的也一样。切割线(就是图中的红线)切割到字符串的结尾位置,说明找到了一个切割方法。这里就是先试一试,第一次切a第二次切aa第三次切aab。这对应的就是回溯里的for循环也就是横向方面。 我们还说回溯仍然会进行递归这里也是一样的第一次切了a剩下的就是“ab。递归就是再将其再切-个回文下来也就是第二个a,剩下的再交给递归进一步切。这就是纵向方面要干的事情其他以此类推。 至于回溯操作与前面是一样的道理不再整述。通过代码就可以发现切割问题的回溯搜索的过程和组合问题的回溯搜索的过程是差不多的。
解析 :
class Solution {ListListString list new ArrayList();ListString temp new ArrayList();public ListListString partition(String s) {dfs(s,0);return list;}public void dfs(String s,int start){if(start s.length()){list.add(new ArrayList(temp));return; }for(int i start;i s.length();i){if(isString(s,start,i)){String tempString s.substring(start,i 1);temp.add(tempString);}else{continue;}dfs(s,i 1);temp.remove(temp.size() - 1);}}public boolean isString(String s,int start,int end){for(int i start, j end;i j;i,j--){if(s.charAt(i) ! s.charAt(j)){return false;}}return true;}
}
