LintCode (108) Palindrome Partitioning II

Given a string s, cut s into some substrings such that every substring is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

Have you met this question in a real interview? 

Yes

Example

For example, given s = "aab",

Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.

又是一道TLE的。。。，先写一个能过小数据的，分析一下再优化

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: /** * @param s a string * @return an integer */ int minCut(string s) { // write your code here int n=s.size(); vector<int> tbl(n+1, INT_MAX); tbl[0]=0; for (int i=1; i<=n; i++){ int val=INT_MAX; for (int j=0; j<i; j++){ if (tbl[j]!=INT_MAX && isPalindrome(s.substr(j, i-j))){ val=min(val,tbl[j]); } tbl[i]=val+1; } } return tbl[n]-1; } bool isPalindrome(const string& s){ int b=0; int e=s.size()-1; while(b<e){ if (s[b++]!=s[e--]) return false; } return true; } };

计算一下有几个palindrome, f[i]为从0 到i的 p串数目， 那么最后cut为f[n]-1.  因为cut么。。。
复杂度是 o(n^3) 因为判断是不是p串是o(n).

一般这种一纬dp，复杂度就是o(n^2)撑死了，除了像爬楼梯那种o(n)的很少见。 所以要过大数据就在判断是不是p串上做手脚。。。

判断一个字符串从i到j其实做了很多重复工作， build一个table。

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 34 35 36 37 38 39 40 41

class Solution { public: /** * @param s a string * @return an integer */ int minCut(string s) { // write your code here int n=s.size(); vector<int> tbl(n+1, INT_MAX); tbl[0]=0; vector<vector<bool>> ptbl(n, vector<bool>(n, false)); buildPTable(ptbl, s); for (int i=1; i<=n; i++){ int val=INT_MAX; for (int j=0; j<i; j++){ if (tbl[j]!=INT_MAX && ptbl[j][i-1]){ val=min(val,tbl[j]); } tbl[i]=val+1; } } return tbl[n]-1; } void buildPTable(vector<vector<bool>>& ptbl, const string& s){ //f[i][j] means from i to j, is p string // initial condition int n=s.size(); for (int i=0; i<n; i++) ptbl[i][i]=true; for (int i=0; i<n-1; i++) ptbl[i][i+1]=s[i] == s[i+1]; for (int len=2; len<n; len++){ for (int b=0; b+len<n; b++){ ptbl[b][b+len]=ptbl[b+1][b+len-1] && s[b]==s[b+len]; } } } };

其实buildTable本身比这个题目有趣一些：

f[i][j]为从i,到j是否为p string
初始条件 对角线上f[i][i]自然是true,因为只有一个字，再就是对角线平移一位，[i][i+1]比较一下，这样做的原因是"bb"这种case也算pstring...

转移方程： f[i][j]如果是true的话，当s[i-1]==s[j+1]的时候， f[i-1][j+1]=true, 反推：
f[i][j]= f[i+1][j-1] && s[i]=s[j]
这个遍历比较有趣，就是外面遍历长度差，从最小为2，一直到真个string,对于每一个长度，我们要选一个起始点，为从0开始来维持对称

其实这个buildTable真要考到我是一时半会想不出，要画一个table,装模作样的列几个例子，然后就开始默写了。。。lol