[LeetCode] Palindrome Partitioning I & II

I put these two questions in one post as the statements are quite similar, even if I solve them use different ideas.

Palindrome Partitioning I:

Problem statement (link here):

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

Analysis:
My first impression is to use DP to solve this problem, we could memoize the palindromes of some substring, and build up the solution, it turned out to be not that easy :-(

I turned to a straightforward DFS recursive method with time complexity O(n^3), space complexity O(n^2).

The idea is like follows:

1, find all palindromes in substring s[0], and all the substrings in s[1:end]
2, find all palindromes in substring s[0:1], and all the substrings in s[2:end]
...
n, find all palindromes in substring s[0:end-1], and all the substrings in s[end]

There are further three things to remember:
1, stop condition: we need to stop when we reach the end in a search;
2, for loop: in each search, we start at the next index of previous found palindrome till end of the entire string;
3, use vector: remember to pop_back();

Code:

class Solution {
public:
    vector<vector<string>> partition(string s) {
        vector<vector<string> > out;
        vector<string> row;
        recur(out, row, s, 0);
        return out;
    }
    void recur(vector<vector<string>>& out, vector<string>& row, string s, int st) {
        if (st==s.size()) {
            out.push_back(row);
            return;
        }
        for (int i=st; i<s.size(); i++) {   // i is the end index
            if (isPalindrome(s, st, i)) {
                row.push_back(s.substr(st, i-st+1));
                recur(out, row, s, i+1);
                row.pop_back();
            }
        }
    }
    bool isPalindrome(string s, int st, int ed) {
        while (st<=ed) {
            if (s[st]==s[ed]) {
                st++; ed--;
            }
            else return false;
        }
        return true;
    }
};

Takeaways:

When you see "return all", "find all possible", "find the total number of", the idea is usually DFS recursive algorithm.

Palindrome Partitioning II:

Problem statement (link here):

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:
We could use the same approach as in Palindrom Partitioning I, which is to recursively search all possibilities and find the minimum number of cuts. However, this naive approach would fail the time test.

Apparently, we should think about how to use DP to solve this problem.

First of all, we will need a DP array to store the number of min-cuts, as we need one extra space for initialization, this dp array should have length (n+1), where n is the length of string s. If we construct the dp array from the end of string s, then dp[i] represents the number of minimum cuts of substring s[i: n-1].

How would we find the min-cuts between i and n-1? Consider the following example,

string:       a   b   a   a   c   a   b   a   b   a   c   c   d   a
str index:  0                       i         j     j+1                    n-1
dp index:  0                       i         j     j+1                    n-1   n

We partition substring s[i: n-1] into two sub-substrings s[i: j] and s[j+1: n-1]. For dp[i], we compare its original dp[i] value with new cut after index j - dp[j+1] + 1, the "1" stands for the one cut cost for new palindrome s[i: j].

Thus, we have the transition function: dp[i] = min(dp[i], dp[j+1] + 1).

Next, consider how we determine a palindrome. In Palindrome Partitioning I, we iteratively check two chars from begin and end, begin-1 and end-1, ... However, if we use a bool 2D DP matrix to record if substring s[i+1: j-1] is a valid substring, and compare only s[i] and s[j] for substring s[i: j], we significantly reduce the number of comparisons. More precisely, we bring down the time complexity with a factor of n.

In sum, the algorithm requires O(n^2) time complexity and O(n^2) space complexity.

Code:

class Solution {
public:
    int minCut(string s) {
        int len=s.length();
        // whether substring between i & j form a palindrome
        bool isPalind[len][len];
        // num of min-cuts from i to n
        int dp[len+1];
        // set initial values
        for (int i=0; i<len; i++)
            for (int j=0; j<len; j++)
                isPalind[i][j]=false;
        // worst case - cut every char
        for (int i=0; i<=len; i++)
            dp[i]=len-i;
        // construct DP array
        for (int i=len-1; i>=0; i--) {
            for (int j=i; j<len; j++) {
                if (s[i]==s[j] && (j-i<2 || isPalind[i+1][j-1])) {
                    isPalind[i][j]=true;
                    dp[i]=min(dp[i],dp[j+1]+1);
                }
            }
        }
        return dp[0]-1;
    }
};

Takeaways:
We should consider DP when asked to find the "optimal" solution.