136.Palindrome Partitioning

1.Description(Medium)

Given a strings, partition_s_such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

Example

Given s ="aab", return:

[
  ["aa","b"],
  ["a","a","b"]
]

2.Code

遇到要求所有组合、可能、排列等解集的题目，一般都是用DFS + backtracking来做。这种需要输出所有结果的基本上都是DFS的解法

https://soulmachine.gitbooks.io/algorithm-essentials/content/java/dfs/palindrome-partitioning.html

//时间复杂度O(2^n)，空间复杂度O(n)
public List<List<String>> partition(String s) {
        List<List<String>>  result=new ArrayList<>();
        ArrayList<String> path=new ArrayList<String>();
        dfs(s,0,path,result);
        return result;        
        }

    public boolean isPalindrome(String s,int start,int end){
        while(start<end){
            if(s.charAt(start)!=s.charAt(end)){
                return false;
            }
            start++;
            end--;
        }
        return true;
    }

    public void dfs(String s,int start,ArrayList<String> path,List<List<String>> result){
        if(start==s.length()){
            result.add(new ArrayList<String>(path));
            return;
        }
        for(int i=start;i<s.length();i++){
            if(isPalindrome(s,start,i)){
                path.add(s.substring(start, i+1));
                dfs(s,i+1,path,result);
                path.remove(path.size()-1);
            }
        }
    }

Palindrome Partition II is Dynamic Programming