132. Palindrome Partitioning II 拆分回文串之二

[GH1995]

132. Palindrome Partitioning II

Difficulty: Hard

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.

[GH1995]

找到把原字符串拆分成回文串的最小切割数

dp[i]表示子串[0, i] 范围内的最小分割数，那么我们最终要返回的就是 dp[n-1] 了，这里先加个corner case的判断，若s串为空，直接返回0

如何更新dp[i]呢，前面说过了其表示子串 [0, i] 范围内的最小分割数。那么这个区间的每个位置都可以尝试分割开来，所以就用一个变量j来从0遍历到i，这样就可以把区间 [0, i] 分为两部分，[0, j-1] 和 [j, i]，那么suppose我们已经知道区间 [0, j-1] 的最小分割数 dp[j-1]，因为我们是从前往后更新的，而 j 小于等于 i，所以 dp[j-1] 肯定在 dp[i] 之前就已经算出来了。这样我们就只需要判断区间 [j, i] 内的子串是否为回文串了，是的话，dp[i] 就可以用 1 + dp[j-1] 来更新了。判断子串的方法用的是之前那道 Palindromic Substrings 一样的方法，使用一个二维的dp数组p，其中 p[i][j] 表示区间 [i, j] 内的子串是否为回文串，其状态转移方程为 p[i][j] = (s[i] == s[j]) && p[i+1][j-1]，其中 p[i][j] = true if [i, j]为回文。这样的话，这道题实际相当于同时用了两个DP的方法

第一个for循环遍历的是i，此时我们现将 dp[i] 初始化为 i，因为对于区间 [0, i]，就算我们每个字母割一刀（怎么听起来像凌迟？！），最多能只用分割 i 次，不需要再多于这个数字。但是可能会变小，所以第二个for循环用 j 遍历区间 [0, j]，根据上面的解释，我们需要验证的是区间 [j, i] 内的子串是否为回文串，那么只要 s[j] == s[i]，并且 i-j < 2 或者 p[j+1][i-1] 为true的话，先更新 p[j][i] 为true，然后在更新 dp[i]，这里需要注意一下corner case，当 j=0 时，我们直接给 dp[i] 赋值为0，因为此时能运行到这，说明 [j, i] 区间是回文串，而 j=0， 则说明 [0, i] 区间内是回文串，这样根本不用分割啊。若 j 大于0，则用 dp[j-1] + 1 来更新 dp[i]，最终返回 dp[n-1] 即可

[GH1995]

// #include "leetcode.h"
class Solution {
 public:
  int minCut(string s) {
    if (s.empty()) return 0;
    int n = s.size();

    vector<vector<bool>> p(n, vector<bool>(n));
    vector<int> dp(n);

    for (int i = 0; i < n; ++i) {
      dp[i] = i; // 初始化拿到外面
      for (int j = 0; j <= i; ++j) {
        if (s[i] == s[j] && (i - j < 2 || p[j + 1][i - 1])) {
          p[j][i] = true;
          dp[i] = (j == 0) ? 0 : min(dp[i], dp[j - 1] + 1);
        }
      }
    }
    return dp[n - 1];
  }
};