132. Palindrome Partitioning II

  • Hardness: Hard\color{red}\textsf{Hard}
  • Ralated Topics: string, dynamic programming

一、題目

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 1:

  • Input: s = “aab”
  • Output: 1
  • Explanation: The palindrome partitioning [“aa”, “b”] could be produced using 1 cut.

Example 2:

  • Input: s = “a”
  • Output: 0

Example 3:

  • Input: s = “ab”
  • Output: 1

Constraints:

  • 1 <= s.length <= 2000
  • s consists of lowercase English letters only.

二、分析

  • 區間型的動態規劃問題，請參考[Algo] 2-5.動態規劃 Dynamic Programming #4 區間型
  • 定義 dp[i] 為 s[0:i] 的 mincut。
    • 當 s[i:j] 為回文時，dp[j] 為 dp[i-1] + 1
    • 當右指標 j 不動時，移動左指標 i，找最小的 minCut，故得動態轉移方程：
      • dp[j] = min(dp[j], dp[i-1]+1)

三、解題

1. DP

  • Time complexity: O(n2)O(n^2)
  • Space complexity: O(n2)O(n^2)
vector<vector<bool>> dp;
void init(string& s) {
    for (int i = 0; i < s.length(); i++) {
        isPalindrome(s, i, i);      // 奇數型
        isPalindrome(s, i, i+1);    // 偶數型
    }
}

int minCut(string& s) {
    int n = s.length();
    dp = vector<vector<bool>>(n, vector<bool>(n, false));
    init(s);   // 將回文先用 memo[left][right] 的方式存起來 
    
    vector<int> cnt(n+1, n-1);      // dp
    cnt[0] = -1;                    // 若問題問可拆為多少組，cnt[0]定為 0，若問需切幾刀，cnt[0]定為 -1
    for (int j = 0; j < n; j++) {
        for (int i = 0; i <= j; i++) {
            if (dp[i][j]) {
                cnt[j+1] = min(cnt[j+1], cnt[i]+1);
            }
        }
    }
    
    return cnt[n];
}
void isPalindrome(string& s, int i, int j) {
    while (i >= 0 && j < s.length()) {
        if (s[i] != s[j]) break;
        dp[i][j] = true;
        i--; 
        j++;
    }
}

回目錄 Catalog