分割回文串

描述 :

給你一個字符串?s，請你將?s?分割成一些子串，使每個子串都是?回文串?。返回?s?所有可能的分割方案。

回文串?是正著讀和反著讀都一樣的字符串。

題目 :

LeetCode 131.分割回文串 :

131. 分割回文串

分析 :
字符串如何判斷回文本身就是一個道算法題，本題在其之上還要再解決一個問題: 如何切割? 如果暴力切割，是非常困難的，如果從回溯的角度來思考就清晰很多:

我們說回溯本身仍然會進行枚舉，這里的也一樣。切割線(就是圖中的紅線)切割到字符串的結尾位置,說明找到了一個切割方法。這里就是先試一試,第一次切a第二次切aa第三次切aab。這對應的就是回溯里的for循環，也就是橫向方面。
我們還說回溯仍然會進行遞歸，這里也是一樣的，第一次切了a剩下的就是“ab"。遞歸就是再將其再切-個回文下來，也就是第二個a,剩下的再交給遞歸進一步切。這就是縱向方面要干的事情，其他以此類推。
至于回溯操作與前面是一樣的道理，不再整述。通過代碼就可以發現，切割問題的回溯搜索的過程和組合問題的回溯搜索的過程是差不多的。

解析 :

class Solution {List<List<String>> list = new ArrayList<>();List<String> temp = new ArrayList<>();public List<List<String>> 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;}
}