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.
Example:
Input: "aab" Output: 1 Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.
Solution: DP
dp[i] := min cuts of s[0~i]
dp[i] = min{dp[j] + 1} if s[j+1~i] is a palindrome.
Time complexity: O(n^2)
Space complexity: O(n^2)
C++
|
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 |
// Author: Huahua class Solution { public: int minCut(string s) { const int n = s.length(); // valid[i][j] = 1 if s[i~j] is palindrome, otherwise 0 vector<vector<int>> valid(n, vector<int>(n, 1)); // dp[i] = min cuts of s[0~i] vector<int> dp(n, n); for (int l = 2; l <= n; ++l) for (int i = 0, j = i + l - 1; j < n; ++i, ++j) valid[i][j] = s[i] == s[j] && valid[i + 1][j - 1]; for (int i = 0; i < n; ++i) { if (valid[0][i]) { dp[i] = 0; continue; } for (int j = 0; j < i; ++j) if (valid[j + 1][i]) dp[i] = min(dp[i], dp[j] + 1); } return dp[n - 1]; } }; |
DP v2
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
// Author: Huahua class Solution { public: int minCut(string s) { const int n = s.length(); // dp[i] = min cuts of s[0~i] vector<int> dp(n, n); for (int m = 0; m < n; ++m) for (int d = 0; d <= 1; ++d) for (int i = m, j = m + d; i >= 0 && j < n && s[i] == s[j]; --i, ++j) dp[j] = min(dp[j], (i ? (dp[i - 1] + 1) : 0)); return dp[n - 1]; } }; |
Related Problems
131. https://zxi.mytechroad.com/blog/searching/leetcode-131-palindrome-partitioning/
1278. https://zxi.mytechroad.com/blog/dynamic-programming/leetcode-1278-palindrome-partitioning-iii/
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment