Palindrome Partitioining LeetCode

这个题是最典型的DFS问题，无奈我对DFS掌握的实在不怎么样。这个题很有可能面试的时候联系Trie问一问，我一定要看下Trie，稍后发总结。

要点： temp当中存的就是没一个DFS伸到最深处，然后把结果存到result里面。

时间复杂度为O(n^2)

public ArrayList<ArrayList<String>> partition(String s) {
        ArrayList<ArrayList<String>> result = new ArrayList<ArrayList<String>>();
        ArrayList<String> temp = new ArrayList<String>();
       
        findPartition(s,0,temp,result);
        return result;
    }
   
    public void findPartition(String s, int begin, ArrayList<String> temp,
        ArrayList<ArrayList<String>> result){
            int len = s.length();
            if (begin >= len) {
                ArrayList<String> copy = new ArrayList<String>();
                for (int j = 0; j < temp.size(); j++){
                    copy.add(temp.get(j));
                }
                result.add(copy);
            }
           
            for (int i = begin; i < len; i++){
                if (isPalindrome(s, begin, i)) {
                    temp.add(s.substring(begin, i+1));
                    findPartition(s, i+1, temp, result);
                    temp.remove(temp.size() - 1);
                }
            }
    }
   
    public boolean isPalindrome(String s, int begin, int end){
        while (begin < end) {
            if (s.charAt(begin++) != s.charAt(end--)) return false;
        }
        return true;
    }