[LeetCode] Palindrome Partitioning I and II(Java)

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

1
2
3
4

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

Palindrome Partitioning II

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

Return the minimum cuts needed for a palindrome partitioning of s.

For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.

Analysis

In these two problem, we often needs to check if the substring(i, j) of the original string is palindrome or not. So we need to save this very important information to an array to prevent checking a same substring for several times. This is a 2-D boolean array which is quite easy to generate. We can generate it from short length to long length. When s.charAt(i) is equal to s.charAt(j), if the array isPalindrome[i + 1][j – 1] is true, then we can update isPalindrome[i][j] = true.

In the first problem, we can use recursive function to generate all possible string lists.

In the second problem, if we use recursive solution, we will got TLE. So a DP solution is needed. We can use a 1-D array D[n] to save the minimum cut. For example, D[i] saves the number of minimum cut of substring(i, n). We can start from i = n – 1, and move i from right to left. When we want to get the D[i] for a new i, we can check every possible substrings from i to n, which means we can use another point j, in which j is between i and n. If substring(i, j) is a palindrome, then we can update D[i] = min(D[i], 1 + D[j + 1]).

This method can also be used in the first problem to save more time.

Code

Palindrome Partitioning (Recursive solution)

public class Solution {
    List<List<String>> ret;
    public List<List<String>> partition(String s) {
        int n = s.length();
        boolean[][] isPalindrome = new boolean[n][n];
        for (int i = 0; i < n; i++)
            isPalindrome[i][i] = true;
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    if (j - i < 2 || isPalindrome[i + 1][j - 1])
                        isPalindrome[i][j] = true;
                }
            }
        }
        ret = new LinkedList<>();
        List<String> list = new LinkedList<>();
        partition(s, 0, isPalindrome, list);
        return ret;
    }
    
    private void partition(String s, int start, boolean[][] isPalindrome, List<String> list) {
        if (start == s.length()) {
            List<String> newList = new LinkedList<>();
            newList.addAll(list);
            ret.add(newList);
            return;
        }
        for (int i = start; i < s.length(); i++) {
            if (isPalindrome[start][i]) {
                list.add(s.substring(start, i + 1));
                partition(s, i + 1, isPalindrome, list);
                list.remove(list.size() - 1);
            }
        }
    }
}

public class Solution {

List<List<String>> ret;

public List<List<String>> partition(String s) {

int n = s.length();

boolean[][] isPalindrome = new boolean[n][n];

for (int i = 0; i < n; i++)

isPalindrome[i][i] = true;

for (int i = n - 1; i >= 0; i--) {

for (int j = i + 1; j < n; j++) {

if (s.charAt(i) == s.charAt(j)) {

if (j - i < 2 || isPalindrome[i + 1][j - 1])

isPalindrome[i][j] = true;

}

ret = new LinkedList<>();

List<String> list = new LinkedList<>();

partition(s, 0, isPalindrome, list);

return ret;

}

private void partition(String s, int start, boolean[][] isPalindrome, List<String> list) {

if (start == s.length()) {

List<String> newList = new LinkedList<>();

newList.addAll(list);

ret.add(newList);

return;

}

for (int i = start; i < s.length(); i++) {

if (isPalindrome[start][i]) {

list.add(s.substring(start, i + 1));

partition(s, i + 1, isPalindrome, list);

list.remove(list.size() - 1);

}

Palindrome Partitioning (DP solution)

import java.lang.reflect.Array;
public class Solution {
    public List<List<String>> partition(String s) {
        int n = s.length();
        boolean[][] isPalindrome = new boolean[n][n];
        for (int i = 0; i < n; i++)
            isPalindrome[i][i] = true;
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    if (j - i < 2 || isPalindrome[i + 1][j - 1])
                        isPalindrome[i][j] = true;
                }
            }
        }
        List<List<String>>[] palindromes = (List<List<String>>[])Array.newInstance(List.class, n + 1);

        palindromes[n] = (List)(new LinkedList<List<String>>());
        List<String> emptyList = new LinkedList<>();
        palindromes[n].add(emptyList);
        for (int i = n - 1; i >= 0; i--) {
            palindromes[i] = (List)(new LinkedList<List<String>>());
            for (int j = i; j < n; j++) {
                if (isPalindrome[i][j]) {
                    List<List<String>> lists = palindromes[j + 1];
                    String substring = s.substring(i, j + 1);
                    for (List<String> list : lists) {
                        List<String> newList = new LinkedList<>();
                        newList.add(substring);
                        newList.addAll(list);
                        palindromes[i].add(newList);
                    }
                }
            }
        }
        return palindromes[0];
    }

}

import java.lang.reflect.Array;

public class Solution {

public List<List<String>> partition(String s) {

int n = s.length();

boolean[][] isPalindrome = new boolean[n][n];

for (int i = 0; i < n; i++)

isPalindrome[i][i] = true;

for (int i = n - 1; i >= 0; i--) {

for (int j = i + 1; j < n; j++) {

if (s.charAt(i) == s.charAt(j)) {

if (j - i < 2 || isPalindrome[i + 1][j - 1])

isPalindrome[i][j] = true;

}

List<List<String>>[] palindromes = (List<List<String>>[])Array.newInstance(List.class, n + 1);

palindromes[n] = (List)(new LinkedList<List<String>>());

List<String> emptyList = new LinkedList<>();

palindromes[n].add(emptyList);

for (int i = n - 1; i >= 0; i--) {

palindromes[i] = (List)(new LinkedList<List<String>>());

for (int j = i; j < n; j++) {

if (isPalindrome[i][j]) {

List<List<String>> lists = palindromes[j + 1];

String substring = s.substring(i, j + 1);

for (List<String> list : lists) {

List<String> newList = new LinkedList<>();

newList.add(substring);

newList.addAll(list);

palindromes[i].add(newList);

}

return palindromes[0];

}

The creation of generic array: http://www.quora.com/Java-programming-language/Why-does-Java-prohibit-generic-array-creation.

Palindrome Partitioning II

public class Solution {
    public int minCut(String s) {
        int n = s.length();
        boolean[][] isPalindrome = new boolean[n][n];
        for (int i = 0; i < n; i++)
            isPalindrome[i][i] = true;
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    if (j - i < 2 || isPalindrome[i + 1][j - 1])
                        isPalindrome[i][j] = true;
                }
            }
        }
        int[] minCut = new int[n + 1];
        for (int i = n; i >= 0; i--)
            minCut[i] = n - 1 - i;
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (isPalindrome[i][j]) {
                    minCut[i] = Math.min(minCut[i], 1 + minCut[j + 1]);
                }
            }
        }
        return minCut[0];
    }
}

public class Solution {

public int minCut(String s) {

int n = s.length();

boolean[][] isPalindrome = new boolean[n][n];

for (int i = 0; i < n; i++)

isPalindrome[i][i] = true;

for (int i = n - 1; i >= 0; i--) {

for (int j = i + 1; j < n; j++) {

if (s.charAt(i) == s.charAt(j)) {

if (j - i < 2 || isPalindrome[i + 1][j - 1])

isPalindrome[i][j] = true;

}

int[] minCut = new int[n + 1];

for (int i = n; i >= 0; i--)

minCut[i] = n - 1 - i;

for (int i = n - 1; i >= 0; i--) {

for (int j = i; j < n; j++) {

if (isPalindrome[i][j]) {

minCut[i] = Math.min(minCut[i], 1 + minCut[j + 1]);

}

return minCut[0];

}

Complexity

In the first problem, assuming the total number of strings is k, then the complexity is $O(n^2 + k)$.

The complexity of second problem is $O(n^2)$.