2.16 Palindrome Partitioning

Description

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"] ]

Method

backtraking dfs

Time and Space Complexity

Code

public class Solution {

public List<List<String>> partition(String s) {
       if (s == null || s.length() == 0){
           return null;
       }
       List<List<String>> ans = new ArrayList<List<String>>();
       helper(ans, new ArrayList<String>(), s, 0);
       return ans;
}

private void helper(List<List<String>> ans, 
                    List<String> path,
                    String s,
                    int pos){
    if (pos == s.length()){
        //System.out.println(pos);
        ans.add(new ArrayList<String>(path));
        return;
    }
    for (int i = pos + 1; i <= s.length(); i++){
         String prefix = s.substring(pos, i);
         if (!isPalindrome(prefix)){
             continue;
         }
         path.add(prefix);
         helper(ans, path, s, i);
         path.remove(path.size() - 1);
    }
}

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

}