Tuesday, November 25, 2014

[LeetCode] Palindrome Partitioning I, II

Palindrome Partitioning I

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


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.


思路:Palindrome Partitioning I

遇到要求所有组合、可能、排列等解集的题目,一般都是用DFS + backtracking来做。要分割回文的前提是能够判断回文。在做DFS的时候,如果每次从start出发查找s[start:end]是否是回文,会使算法复杂度大大增加。而在Longest Palindromic Substring这题中已经知道如何用DP来计算任意s[i:j]是否是回文。因此可以先计算该判断矩阵,在DFS的时候用来剪枝,大大提高效率。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    vector<vector<string>> partition(string s) {
        int n = s.size();
        vector<vector<string>> ret;
        vector<string> sol;
        vector<vector<bool>> isPal(n, vector<bool>(n,false));
        for(int i=n-1; i>=0; i--) {
            for(int j=i; j<n; j++) {
                if((i+1>=j-1 || isPal[i+1][j-1]) && s[i]==s[j])
                    isPal[i][j] = true;
            }
        }
        findPartitions(s, 0, isPal, sol, ret);
        return ret; 
    }
    
    void findPartitions(string &s, int start, vector<vector<bool>> &isPal, vector<string> &sol, vector<vector<string>> &ret) {
        if(start==s.size()) {
            ret.push_back(sol);
            return;
        }
        
        for(int i=start; i<s.size(); i++) {
            if(isPal[start][i]) {
                int len = i-start+1;
                sol.push_back(s.substr(start, len));
                findPartitions(s, i+1, isPal, sol, ret);
                sol.pop_back();
            }
        }
    }
};


思路:Palindrome Partitioning II

整体的思路是一维DP。DP[i]表示长度为i的prefix:s[0: i-1]的min cut数量。
DP[i] = min (DP[j] + 1) ,对所有 0<=j<i,且s[j: i-1]为palindrome。
和I同样的技巧,用DP先计算存储一个palindrome判断矩阵isPal[i][j],便于后面一维DP计算中能迅速判断s[j: i-1]是否为palindrome。

有一个更优的解法参考:
https://oj.leetcode.com/discuss/9476/solution-does-not-need-table-palindrome-right-uses-only-space

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int minCut(string s) {
        int n = s.size();
        if(n<=1) return 0;
        vector<vector<bool>> isPal(n, vector<bool>(n, false));
        for(int i=n-1; i>=0; i--) {
            for(int j=i; j<n; j++) {
                if((i+1>j-1 || isPal[i+1][j-1]) && s[i]==s[j])
                    isPal[i][j] = true;
            }
        }
        
        vector<int> dp(n+1,INT_MAX);
        dp[0] = -1;
        for(int i=1; i<=n; i++) {
            for(int j=i-1; j>=0; j--) {
                if(isPal[j][i-1]) {
                    dp[i] = min(dp[i], dp[j]+1);
                }
            }
        }
        return dp[n];
    }
};

4 comments:

  1. 第一种算法,计算dp也需要O(n^2),所以时间复杂度貌似没有变小

    ReplyDelete
    Replies
    1. 用Big O notation来表示复杂度时,给出的是复杂度的数量级,却掩盖了这个数量级前的常数系数。而往往这个系数的大小,也能决定了是否过的了大数据测试。

      Delete
  2. This is my discussion and Java implementation http://www.capacode.com/dynamic-programming/split-string-into-palindromes/. You can also find testcases to test your program.

    ReplyDelete