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

Solution:

We can use dynamic programming to calculate all the possible substrings if they are palindrome or not and save them in a matrix. Then we use backtracking to generate all the possible partitions.

public class Solution {
    public List<List<String>> partition(String s) {
        boolean [][] isPalindrome = new boolean[s.length()][s.length()];
        for(int length = 0; length < s.length(); length++)
        {
            for(int start = 0; start < s.length()-length; start++)
            {
                if(length==0)
                    isPalindrome[start][start+length] = true;
                else if(length==1)
                    isPalindrome[start][start+length] = s.charAt(start)==s.charAt(start + length);
                else
                    isPalindrome[start][start+length] = isPalindrome[start+1][start+length-1] && s.charAt(start)==s.charAt(start + length);
            }
        }
        
        List<List<String>> solution = new ArrayList<List<String>>();
        partition(s, 0, isPalindrome, new ArrayList<String>(), solution);
        return solution;
    }
    
    private void partition(String s, int index, boolean[][] isPalindrome, ArrayList<String> tempSolution, List<List<String>> solution)
    {
        if(index==s.length())
        {
            solution.add((List<String>) tempSolution.clone());
            return;
        }
        for(int i= index; i<s.length();i++)
        {
            if(isPalindrome[index][i])
            {
                tempSolution.add(s.substring(index,i+1));
                partition(s, i+1, isPalindrome, tempSolution, solution);
                tempSolution.remove(tempSolution.size()-1);
            }
        }
    }
}