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 =
Return
"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 =
Return
"aab"
,Return
1
since the palindrome partitioning ["aa","b"]
could be produced using 1 cut.
遇到要求所有组合、可能、排列等解集的题目,一般都是用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
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]; } }; |
第一种算法,计算dp也需要O(n^2),所以时间复杂度貌似没有变小
ReplyDelete用Big O notation来表示复杂度时,给出的是复杂度的数量级,却掩盖了这个数量级前的常数系数。而往往这个系数的大小,也能决定了是否过的了大数据测试。
DeleteThis 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