LeetCode 131. Palindrome Partitioning

原题链接在这里：https://leetcode.com/problems/palindrome-partitioning/

题目：

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example, given s = "aab",
Return

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

题解：

backtracking问题, dfs时当前一段如果是Palindrome就加进item. 然后递归调用helper, 递归终止条件是能正好走到s.length().

Time Complexity: exponential. 

Space: O(res.size()).

AC Java:

public class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> res = new ArrayList<List<String>>();
        if(s == null || s.length() == 0){
            return res;
        }
        helper(s,0, new ArrayList<String>(),res);  
        return res;
    }
    private void helper(String s, int start,List<String> item, List<List<String>> res){
        if(start == s.length()){
            res.add(new ArrayList(item));
            return;
        }
        StringBuilder sb = new StringBuilder();
        for(int i = start; i <s.length(); i++){
            sb.append(s.charAt(i));
            if(isPalindrome(sb.toString())){
                item.add(sb.toString());
                helper(s,i+1,item,res);
                item.remove(item.size()-1);
            }
        }
    }
    private boolean isPalindrome(String s){
        if(s == null || s.length() == 0){
            return true;
        }
        int i = 0;
        int j = s.length()-1;
        while(i<j){
            if(s.charAt(i) != s.charAt(j)){
                return false;
            }
            i++;
            j--;
        }
        return true;
    }
}

类似Word Break II, Subsets.

跟上Palindrome Partitioning II.