LeetCode 1278. 分割回文串 III

截止到目前我已經寫了 600多道演算法題，其中部分已經整理成了pdf檔案，目前總共有1000多頁（并且還會不斷的增加），大家可以免費下載
下載鏈接：https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取碼：6666

371，背包問題系列之-基礎背包問題

//字串的子串[left,right]變成回文串所需要修改的字符數
private int change(String s, int left, int right) {
    int count = 0;
    while (left < right) {
        //如果兩個指標指向的字符相同，我們不需要修改，
        //如果不相同，只需要修改其中的一個即可，所以
        // 修改數要加1
        if (s.charAt(left++) != s.charAt(right--))
            count++;
    }
    return count;
}

分析到這里，這題的代碼基本上就呼之欲出了，我們來看下完整代碼

public int palindromePartition(String s, int k) {
    int length = s.length();
    //dp[i][j]表示s的前i個字符分割成k個子串所修改的最少字符數，
    int[][] dp = new int[length + 1][k + 1];
    //因為這題要求的是所需要修改的最少字符數，初始值我們賦值盡可能大
    for (int i = 0; i < dp.length; i++) {
        Arrays.fill(dp[i], length);
    }
    //前i個字符，分割成j個回文子串
    for (int i = 1; i <= length; i++) {
        //前i個字符最大只能分割成i個子串，所以不能超過i，
        //我們取i和k的最小值
        int len = Math.min(i, k);
        for (int j = 1; j <= len; j++) {
            if (j == 1) {
                //如果j等于1，則表示沒有分割，我們直接計算
                dp[i][j] = change(s, j - 1, i - 1);
            } else {
                //如果j不等于1，我們計算分割所需要修改的最小字符數，因為m的值要
                //大于等于j-1，我們就從最小的開始列舉
                for (int m = j - 1; m < i; m++) {
                    //遞推公式
                    dp[i][j] = Math.min(dp[i][j], dp[m][j - 1] + change(s, m, i - 1));
                }
            }
        }
    }
    //回傳前length個字符分割成k個子串所需要修改的最少字符數
    return dp[length][k];
}

//字串的子串[left,right]變成回文串所需要修改的字符數
private int change(String s, int left, int right) {
    int count = 0;
    while (left < right) {
        //如果兩個指標指向的字符相同，我們不需要修改，
        //如果不相同，只需要修改其中的一個即可，所以
        // 修改數要加1
        if (s.charAt(left++) != s.charAt(right--))
            count++;
    }
    return count;
}

public int palindromePartition(String s, int k) {
    int length = s.length();

    //palindrome[i][j]表示子串[i,j]轉化為回文串所需要的修改的字符數
    int[][] palindrome = new int[length][length];
    //2種實作方式
    //        //一列一列的從左往右（只遍歷右上部分）
    //        for (int j = 1; j < length; j++) {
    //            for (int i = 0; i < j; i++) {
    //                palindrome[i][j] = palindrome[i + 1][j - 1] + (s.charAt(i) == s.charAt(j) ? 0 : 1);
    //            }
    //        }

    //一行一行的從下往上（只遍歷右上部分）
    for (int i = length - 2; i >= 0; i--) {
        for (int j = i + 1; j < length; j++) {
            palindrome[i][j] = palindrome[i + 1][j - 1] + (s.charAt(i) == s.charAt(j) ? 0 : 1);
        }
    }

    //dp[i][j]表示s的前i個字符分割成k個回文子串的最少次數,
    //第一行和第一列應該都是0，
    int[][] dp = new int[length + 1][k + 1];
    for (int i = 1; i < dp.length; i++) {
        Arrays.fill(dp[i], Integer.MAX_VALUE);
    }
    //前i個字符，分割成j個回文子串
    for (int i = 1; i <= length; i++) {
        int len = Math.min(i, k);
        for (int j = 1; j <= len; j++) {
            if (j == 1)//字串的下標是從0開始的，所以這里要減1
                dp[i][j] = palindrome[j - 1][i - 1];
            else
                for (int m = j - 1; m < i; m++) {
                    dp[i][j] = Math.min(dp[i][j], dp[m][j - 1] + palindrome[m][i - 1]);
                }
        }
    }
    return dp[length][k];
}

因為dp[i][j]中i必須大于等于j，所以這里遍歷的時候可以有兩種方式，如下圖所示

總結

LeetCode上分隔回文串總共有4題，其中只有一道中等，其他3道都是困難，這里把這4道都講完了，也可以一起看下前面的3道題，

551，回溯演算法解分割回文串

553，動態規劃解分割回文串 II

570，動態規劃解回文串分割 IV