Palindrome Partitioning II
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 42 43
| int dp[505][505];
int helper(string& s, int l, int r) { if(l == r) return 0; if(dp[l][r] != -1) return dp[l][r]; int& res = dp[l][r] = INT_MAX; for(int i = l; i < r; i++) { res = min(res, 1 + helper(s,l,i) + helper(s,i + 1, r)); } return res; }
void manacher(string s) { string ss = "#"; for(auto& ch : s) { ss.push_back(ch); ss.push_back('#'); } int l = 0, r = -1, n = ss.length(); vector<int> mana(n); for(int i = 0; i < n; i++) { mana[i] = max(0, min(r - i, (r + l - i >= 0 ? mana[r + l - i] : -1))); while(i + mana[i] < n and i - mana[i] >= 0 and ss[i + mana[i]] == ss[i - mana[i]]) mana[i]++; if(i + mana[i] > r) { r = i + mana[i]; l = i - mana[i]; } } for(int i = 0; i < n; i++) { int l = i - mana[i] + 1, r = i + mana[i] - 1; while(l < r) { if(ss[l] != '#' and ss[r] != '#') dp[l/2][r/2] = 0; l++,r--; } } }
int Solution::minCut(string A) { memset(dp,-1,sizeof dp); manacher(A); return helper(A,0,A.length() - 1); }
|