LeetCode-132. 分割回文串 II

132. 分割回文串 II

給你一個字元串

s

，請你将

s

分割成一些子串，使每個子串都是回文。

傳回符合要求的 最少分割次數 。

示例 1：

輸入：s = "aab"
輸出：1
解釋：隻需一次分割就可将 s 分割成 ["aa","b"] 這樣兩個回文子串。
           

示例 2：

輸入：s = "a"
輸出：0
           

分析階段

動态規劃

把字元串分割成多個子串，要求所有子串是回文串，傳回最少的分割次數。最直接的做法是，把所有的子串都列舉出來，從中找到最少的一種組合。題目 131. 分割回文串 就是找到所有的回文串組合，但是使用這種方法在 LeetCode 送出結果如下，需要使用新的解法：

假設字元串 s s s 隻有一種分割方法，如下所示：

s [ 0 , i 1 ] , s [ i 1 + 1 , i 2 ] , s [ i 2 + 1 , i 3 ] , . . . , s [ i k − 1 , i k ] , s [ i k + 1 , n − 1 ] s[0,i_1],s[i_1+1,i_2],s[i_2+1,i_3],...,s[i_{k-1},i_k],s[i_k+1,n-1] s[0,i1​],s[i1​+1,i2​],s[i2​+1,i3​],...,s[ik−1​,ik​],s[ik​+1,n−1]，分割次數 k k k

可以看出，如果 s [ i k + 1 , n − 1 ] s[i_k+1,n-1] s[ik​+1,n−1] 是回文串，那麼 s [ 0 , n − 1 ] s[0,n-1] s[0,n−1]的最少分割次數就是 “ s [ 0 , k ] s[0,k] s[0,k]的最少分割次數加1”。

如果字元串 s s s有多種分割方法，假設有三種方法，如下所示：

1、 s [ 0 , i 11 ] , s [ i 11 + 1 , i 1 2 ] , s [ i 12 + 1 , i 13 ] , . . . , s [ i k 1 − 1 , i k 1 ] , s [ i k 1 + 1 , n − 1 ] s[0,i_{11}],s[i_{11}+1,i_12],s[i_{12}+1,i_{13}],...,s[i_{k1-1},i_{k1}],s[i_{k1}+1,n-1] s[0,i11​],s[i11​+1,i1​2],s[i12​+1,i13​],...,s[ik1−1​,ik1​],s[ik1​+1,n−1]，分割次數 k 1 k1 k1

2、 s [ 0 , i 21 ] , s [ i 21 + 1 , i 22 ] , s [ i 22 + 1 , i 23 ] , . . . , s [ i k 2 − 1 , i k 2 ] , s [ i k 2 + 1 , n − 1 ] s[0,i_{21}],s[i_{21}+1,i_{22}],s[i_{22}+1,i_{23}],...,s[i_{k2-1},i_{k2}],s[i_{k2}+1,n-1] s[0,i21​],s[i21​+1,i22​],s[i22​+1,i23​],...,s[ik2−1​,ik2​],s[ik2​+1,n−1]，分割次數 k 2 k2 k2

3、 s [ 0 , i 31 ] , s [ i 31 + 1 , i 32 ] , s [ i 32 + 1 , i 33 ] , . . . , s [ i k 3 − 1 , i k 3 ] , s [ i k 3 + 1 , n − 1 ] s[0,i_{31}],s[i_{31}+1,i_{32}],s[i_{32}+1,i_{33}],...,s[i_{k3-1},i_{k3}],s[i_{k3}+1,n-1] s[0,i31​],s[i31​+1,i32​],s[i32​+1,i33​],...,s[ik3−1​,ik3​],s[ik3​+1,n−1]，分割次數 k 3 k3 k3

要找到最少的分割次數，就是在 k 1 、 k 2 、 k 3 k1、k2、k3 k1、k2、k3 中找到最小值，而 k 1 、 k 2 、 k 3 k1、k2、k3 k1、k2、k3 分别是 s [ 0 , i k 1 ] 、 s [ 0 , i k 2 ] 、 s [ 0 , i k 3 ] s[0,i_{k1}]、s[0,i_{k2}]、s[0,i_{k3}] s[0,ik1​]、s[0,ik2​]、s[0,ik3​] 的最少分割次數加1。

是以，問題的子問題就為：在 s [ 0 , i k 1 ] 、 s [ 0 , i k 2 ] 、 s [ 0 , i k 3 ] s[0,i_{k1}]、s[0,i_{k2}]、s[0,i_{k3}] s[0,ik1​]、s[0,ik2​]、s[0,ik3​]的分割次數中找到最小值，并且 s [ 0 , i k 1 ] 、 s [ 0 , i k 2 ] 、 s [ 0 , i k 3 ] s[0,i_{k1}]、s[0,i_{k2}]、s[0,i_{k3}] s[0,ik1​]、s[0,ik2​]、s[0,ik3​]的分割次數也可以通過求解它們的子問題得到。

1、問題類型

第二類：對某種資料結構和算法的使用

使用的算法：動态規劃

資料結構：構造狀态數組

2、解題思路

從前面已經知道，在 s [ 0 , n − 1 ] s[0,n-1] s[0,n−1] 範圍内找到最少分割次數，就是要找到所有的回文子串下标 k ( k 1 、 k 2 、 k 3.... ) k(k1、k2、k3....) k(k1、k2、k3....)， s [ 0 , n − 1 ] s[0,n-1] s[0,n−1] 的最少分割次數等于$ s[0,k1]、s[0,k2]、s[0,k3]、… $ 中最小分割次數加1。

是以，我們可以構造一個數組，使用動态規劃來求解最少分割次數，求解過程如下：

1、要求解的“狀态”是：到字元串任意下标 i i i 處， s [ 0 , i ] s[0,i] s[0,i] 的最少的回文子串分割次數；

2、簡化狀态，得到“base case”： i = = 0 i == 0 i==0 或者 s [ 0 , i ] s[0,i] s[0,i] 本身就是回文串，分割次數為0；

3、構造“數組”：構造數組 d p [ n ] dp[n] dp[n]​​​， d p [ i ] dp[i] dp[i]​​​ 表示子串 s [ 0 , i ] s[0,i] s[0,i]​​​ 的最少分割次數；

4、構造狀态轉移方程：

d p [ i ] = { 0 , s [ 0 , i ]    是回文子串 m i n { d p [ k ] } , k < i    a n d    s [ k , i ]    是回文子串 dp[i]= \begin{cases} 0, & s[0,i]\; \text{是回文子串} \\[2ex] min\{dp[k]\}, & k < i\; and\; s[k,i]\;\text{是回文子串} \end{cases} dp[i]=⎩⎨⎧​0,min{dp[k]},​s[0,i]是回文子串k<iands[k,i]是回文子串​

從“構造函數”可以看出，在确定 d p [ i ] dp[i] dp[i] 的值之前，要先知道所有 $dp[k](k \le i) $的值，是以在周遊字元串時，外層下标 i i i 從0開始周遊到 n n n，内層下标 k k k 從0開始周遊到 i i i。另外，我們要知道 s [ k , i ] s[k,i] s[k,i] 是否是回文子串，可以使用題目 5. 最長回文子串 構造的二維數組。

代碼實作在“編碼階段”，在 LeetCode 的送出結果如下：

編碼階段

class Solution {
    public int minCut(String s) {
        int n = s.length();
        boolean[][] isPalindrome = isPalindrome(s);
        int[] dp = new int[n];
        // 初始值
        Arrays.fill(dp, Integer.MAX_VALUE);

        for (int i = 0; i < n; i++) {
            if (isPalindrome[0][i]) {
                dp[i] = 0;
            } else {
                for (int k = 0; k < i; k++) {
                    if (isPalindrome[k + 1][i]) {
                        // 依次周遊下标 k，取出最小值
                        dp[i] = Math.min(dp[i], dp[k] + 1);
                    }
                }
            }
        }
        return dp[n - 1];
    }

    private boolean[][] isPalindrome(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (i == j) {
                    dp[i][j] = true;
                } else {
                    boolean b = s.charAt(i) == s.charAt(j);
                    if (j == i + 1) {
                        dp[i][j] = b;
                    } else {
                        dp[i][j] = b & dp[i + 1][j - 1];
                    }
                }
            }
        }
        return dp;
    }
}
           

總結階段

“分割回文串II”解題思路：

1、先用一個簡單的例子，找到問題的子問題：最少次數是在多個回文子串中取最小值加1，再不斷縮小子問題；

2、構造狀态數組，直接儲存狀态： s [ 0 , i ] s[0,i] s[0,i] 的最少分割次數。