LeetCode Palindrome Partitioning I and II: Backtracking (DFS) and DP

Overview

LeetCode Palindrome Partitioning I and II: we use Backtracking (DFS) to solve the first problem and dynamic programming (DP) to tackle the second follow up.

LeetCode Palindrome Partitioning I and II

(1)

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

(2)
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.

Solution and Precautions: Backtracking (DFS) and DP

(1) could be solve by DFS to enumerate all the possible partitions. The following Java code is accepted by LeetCode OJ to pass this Palindrome Partitioning I problem:

public class Solution {

    List<List<String>> dfs(String s, int i, boolean [][] isPalindrome) {
        if (i >= s.length())
            return null;

        List<List<String>> result = new ArrayList<List<String>>();

        for (int j = i, n = s.length(); j < n; ++j) {
            if (isPalindrome[i][j]) {
                String cut = s.substring(i, j + 1);
                List<List<String>> others = dfs(s, j + 1, isPalindrome);
                if (null != others) {
                    for (List<String> l : others) {
                        l.add(0, cut);
                        result.add(l);
                    }
                }
                else {
                    List<String> ll = new LinkedList<String>();
                    ll.add(cut);
                    result.add(ll);
                }
            }
        }
        return result;
    }

    public List<List<String>> partition(String s) {
        int n = s.length();
        boolean [][] isPalindrome = new boolean [n][n];
        for (int i = 0; i < n; ++i)
            for (int j = i; j >= 0; --j)
                isPalindrome[i][j] = true;

        for (int len = 2; len <= n; ++len)
            for (int i = 0, j = i + len - 1; j < n; ++i, ++j)
                isPalindrome[i][j] = (s.charAt(i) == s.charAt(j) && isPalindrome[i+1][j-1]);

        return dfs(s, 0, isPalindrome);
    }
}

(2) will need to use dp for both the final result and the check of palindromic property.

Let F(i) = min cut for s[i]…s[n-1] so F(0) is our answer and we have:

F(i) = min(1 + F(j))  for j = i + 1, …  n-1 and s[i]…s[j-1] is palidromic
F(i) = 0    if s[i]…s[n-1] is palindromic

To test if a substring is palindromic we again adopt dp appraoch, that is S[i]…S[j] is palindromic if and only if S[i] == S[j] and S[i+1]…S[j-1] is palindromic, the total time would be O(N^2). The following Java code is accepted by LeetCode OJ to pass this Palindrome Partitioning II problem:

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)
            for (int j = i; j >= 0; --j)
                isPalindrome[i][j] = true;

        for (int len = 2; len <= n; ++len)
            for (int i = 0, j = i + len - 1; j < n; ++i, ++j)
                isPalindrome[i][j] = (s.charAt(i) == s.charAt(j) && isPalindrome[i+1][j-1]);

        int [] dp = new int[n];
        dp[n-1] = 0;
        for (int i = n - 2; i >= 0; --i) {
            if (isPalindrome[i][n-1])
                dp[i] = 0;
            else {
                dp[i] = 1 + dp[i+1];
                for (int j = i + 1; j < n; ++j) {
                    if (isPalindrome[i][j]) {
                        dp[i] = Math.min(dp[i], 1 + dp[j+1]);
                    }
                }
            }
        }
        return dp[0];
    }
}

Remarks:

  1. for the dp formula, it is attempting to come up with a linear time solution by keeping the minimum cut among dp[i] … dp[n-1], but this minimum cut value is useless since the correct value depends on different cases by testing the palindrome sub-string, there is no such a constant time approach to get such minimum value to my knowledge.
  2. And for the first problem, do not try to copy back the results by frequently new objects in Java which might give you memory limit exceeds error from LeetCode OJ.

Summary

LeetCode Palindrome Partitioning I and II: we use Backtracking (DFS) to solve the first problem and dynamic programming (DP) to tackle the second follow up.

Written on June 5, 2013