【hot100-java】【分割回文串】

回溯篇

class Solution {//ret是需要返回的结果//path是回溯过程中的记录private final List<List<String>> ret=new ArrayList<>();private final List<String> path = new ArrayList<>();private String s;public List<List<String>> partition(String s) {this.s=s;dfs(0,0);return ret;}//start表示这段回文子串的开始位置private void dfs(int i,int start){//结束的时候将path赋给retif (i==s.length()){ret.add(new ArrayList<>(path));return;}//1.不选i和i+1之间的逗号(i=n-1时一定需要选)if(i<s.length()-1){dfs(i+1,start);}//2.选i和i+1之间的逗号(s[i]作为子串最后一个字符)if (isPalindrome(start,i)){path.add(s.substring(start,i+1));//下一个子串从i+1开始dfs(i+1,i+1);//恢复现场path.remove(path.size()-1);}}private boolean isPalindrome(int left,int right){while(left<right){if(s.charAt(left++)!=s.charAt(right--)){return false;}}return true;}
}