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.
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
| 这里用到了两个dp, 一个是判断字符串s[i][j]是否为回文, 一个是记录s[0..i]最小的切割数 经典题 */ class Solution { public: int minCut(string s) { int n = s.size(); vector<vector<bool> > isPal(n, vector<bool>(n, false)); vector<int> cut(n, 0); for (int j = 0; j < n; j++) { cut[j] = j; for (int i = 0; i <= j; i++) { if (s[i] == s[j] && (j - i <= 1 || isPal[i + 1][j - 1])) { isPal[i][j] = true; if (i > 0) cut[j] = min(cut[j], cut[i - 1] + 1); else cut[j] = 0; } } } return cut[n - 1]; } };
|