[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]; } };