131 Palindrome Partitioning

　輸入一個字符串s，將s分割為n個子串，每個子串都是一個回文。返回s有多少種分割方式。
　例如輸入：“aab”
　輸出：[
[“aa”,”b”],
[“a”,”a”,”b”]
]
　思路：這是一個不斷將問題規模變小的問題。有點動態規劃的味道。
問題1 對”aab”切分子串。首先可以看做是 “a” 和”ab”切分。第一部分”a”切分確定，并且”a”是一個回文，”ab”作為輸入字符串再次回到原問題。
問題1-1 對”ab”切分子串。不斷遞歸直到輸入字符串為0。
再次回到問題1。第二可以看做是 “aa” 和”b”切分。第一部分”aa”切分確定，并且”aa”是一個回文，”b”作為輸入字符串再次回到原問題。
問題1-2 對”b”切分子串。
…..不斷下去。

partition(“abc”) =[ “a” + partition(“bc”)] + [ “aa” + partition(“c”)] + [ “aab” + partition(“”)]
partition(“bc”)=[“b”+partition(“c”)]
partition(“c”)=”c”
partition(“”) 添加答案，直接退出。

private List<List<String>> resultList = new ArrayList<List<String>>();public List<List<String>> partition(String s) {resultList.clear();doPartition(s,new ArrayList<String>());return resultList;}private void doPartition(String s,List<String> result){if(s==""){List<String> n = new ArrayList<String>();n.addAll(result);resultList.add(n);return;}int startIdx = 0;for(int endIdx = 1;endIdx<s.length();endIdx++){String subString = s.substring(startIdx,endIdx);if(isPalindrome(subString)){result.add(subString);doPartition(s.substring(endIdx),result);result.remove(result.size()-1);}}if(isPalindrome(s)){result.add(s);doPartition("",result);result.remove(result.size()-1);}}private boolean isPalindrome(String s){int mid = s.length()/2;int end = s.length()-1;for(int i=0;i<mid;i++){if(s.charAt(i)!=s.charAt(end-i)){return false;}}return true;}

改進

　思路一模一樣，只是在處理的時候盡量少使用String的substring方法。參考鏈接。substring會創建一個新的String對象，同時有一個數組拷貝的動作。該版本的速度大大提升。
　

private List<List<String>> resultList = new ArrayList<List<String>>();public List<List<String>> partition(String s) {resultList.clear();doPartition(s,0,new ArrayList<String>());return resultList;}private void doPartition(String s,int leftIdx,List<String> result){if(leftIdx==s.length()){List<String> n = new ArrayList<String>();n.addAll(result);resultList.add(n);return;}for(int endIdx = leftIdx;endIdx<s.length();endIdx++){if(isPalindrome(s,leftIdx,endIdx)){result.add(s.substring(leftIdx,endIdx+1));doPartition(s,endIdx+1,result);result.remove(result.size()-1);}}}private boolean isPalindrome(String s,int l,int r){if(l==r) return true;while(l<r){if(s.charAt(l)!=s.charAt(r)){return false;}l++;r--;}return true;}

總結

以上是生活随笔為你收集整理的leetcode之回溯backtracing专题4的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。