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

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.

這道題是讓找到把原字符串拆分成回文串的最小切割數(shù)，如果我們首先考慮用brute force來做的話就會(huì)十分的復(fù)雜，因?yàn)槲覀儾坏袛嘧哟欠袷腔匚拇?，而且還要找出最小切割數(shù)，情況會(huì)非常的多，不好做。所以對(duì)于這種玩字符串且是求極值的題，就要祭出曠古神器動(dòng)態(tài)規(guī)劃Dynamic Programming了，秒天秒地秒空氣，DP在手天下我有。好，吹完一波后，開始做題。DP解法的兩個(gè)步驟，定義dp數(shù)組和找狀態(tài)轉(zhuǎn)移方程。首先來定義dp數(shù)組，這里使用最直接的定義方法，一維的dp數(shù)組，其中dp[i]表示子串 [0, i] 范圍內(nèi)的最小分割數(shù)，那么我們最終要返回的就是 dp[n-1] 了，這里先加個(gè)corner case的判斷，若s串為空，直接返回0，OJ的test case中并沒有空串的檢測(cè)，但博主認(rèn)為還是加上比較好，畢竟空串也算是回文串的一種，所以最小分割數(shù)為0也說得過去。接下來就是大難點(diǎn)了，如何找出狀態(tài)轉(zhuǎn)移方程。

如何更新dp[i]呢，前面說過了其表示子串 [0, i] 范圍內(nèi)的最小分割數(shù)。那么這個(gè)區(qū)間的每個(gè)位置都可以嘗試分割開來，所以就用一個(gè)變量j來從0遍歷到i，這樣就可以把區(qū)間 [0, i] 分為兩部分，[0, j-1] 和 [j, i]，那么suppose我們已經(jīng)知道區(qū)間 [0, j-1] 的最小分割數(shù) dp[j-1]，因?yàn)槲覀兪菑那巴蟾碌模?j 小于等于 i，所以 dp[j-1] 肯定在 dp[i] 之前就已經(jīng)算出來了。這樣我們就只需要判斷區(qū)間 [j, i] 內(nèi)的子串是否為回文串了，是的話，dp[i] 就可以用 1 + dp[j-1] 來更新了。判斷子串的方法用的是之前那道 Palindromic Substrings 一樣的方法，使用一個(gè)二維的dp數(shù)組p，其中 p[i][j] 表示區(qū)間 [i, j] 內(nèi)的子串是否為回文串，其狀態(tài)轉(zhuǎn)移方程為 p[i][j] = (s[i] == s[j]) && p[i+1][j-1]，其中 p[i][j] = true if [i, j]為回文。這樣的話，這道題實(shí)際相當(dāng)于同時(shí)用了兩個(gè)DP的方法，確實(shí)難度不小呢。

第一個(gè)for循環(huán)遍歷的是i，此時(shí)我們現(xiàn)將 dp[i] 初始化為 i，因?yàn)閷?duì)于區(qū)間 [0, i]，就算我們每個(gè)字母割一刀（怎么聽起來像凌遲？?。疃嗄苤挥梅指?i 次，不需要再多于這個(gè)數(shù)字。但是可能會(huì)變小，所以第二個(gè)for循環(huán)用 j 遍歷區(qū)間 [0, j]，根據(jù)上面的解釋，我們需要驗(yàn)證的是區(qū)間 [j, i] 內(nèi)的子串是否為回文串，那么只要 s[j] == s[i]，并且 i-j < 2 或者 p[j+1][i-1] 為true的話，先更新 p[j][i] 為true，然后在更新 dp[i]，這里需要注意一下corner case，當(dāng) j=0 時(shí)，我們直接給 dp[i] 賦值為0，因?yàn)榇藭r(shí)能運(yùn)行到這，說明 [j, i] 區(qū)間是回文串，而 j=0， 則說明 [0, i] 區(qū)間內(nèi)是回文串，這樣根本不用分割啊。若 j 大于0，則用 dp[j-1] + 1 來更新 dp[i]，最終返回 dp[n-1] 即可，參見代碼如下：

解法一：

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];
    }
};

我們也可以反向推，這里的dp數(shù)組的定義就剛好跟前面反過來了，dp[i] 表示區(qū)間 [i, n-1] 內(nèi)的最小分割數(shù)，所以最終只需要返回 dp[0] 就是區(qū)間 [0, n-1] 內(nèi)的最喜哦啊分割數(shù)了，極為所求。然后每次初始化 dp[i] 為 n-1-i 即可，j 的更新范圍是 [i, n)，此時(shí)我們就只需要用 1 + dp[j+1] 來更新 dp[i] 了，為了防止越界，需要對(duì) j == n-1 的情況單獨(dú)處理一下，整個(gè)思想跟上面的解法一模一樣，請(qǐng)參見之前的講解。

解法二：

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 = n - 1; i >= 0; --i) {
            dp[i] = n - i - 1;
            for (int j = i; j < n; ++j) {
                if (s[i] == s[j] && (j - i <= 1 || p[i + 1][j - 1])) {
                    p[i][j] = true;
                    dp[i] = (j == n - 1) ? 0 : min(dp[i], dp[j + 1] + 1);
                }
            }
        }
        return dp[0];
    }
};

下面這種解法是論壇上的高分解法，沒用使用判斷區(qū)間 [i, j] 內(nèi)是否為回文串的二維dp數(shù)組，節(jié)省了空間。但寫法上比之前的解法稍微有些凌亂，也算是個(gè) trade-off 吧。這里還是用的一維dp數(shù)組，不過大小初始化為了 n+1，這樣其定義就稍稍發(fā)生了些變化，dp[i] 表示由s串中前 i 個(gè)字母組成的子串的最小分割數(shù)，這樣 dp[n] 極為最終所求。接下來就要找狀態(tài)轉(zhuǎn)移方程了。這道題的更新方式比較特別，跟之前的都不一樣，之前遍歷 i 的時(shí)候，都是更新的 dp[i]，這道題更新的卻是 dp[i+len+1] 和 dp[i+len+2]，其中 len 是以i為中心，總長(zhǎng)度為 2*len + 1 的回文串，比如 bob，此時(shí) i=1，len=1，或者是i為中心之一，總長(zhǎng)度為 2*len + 2 的回文串，比如 noon，此時(shí) i=1，len=1。中間兩個(gè)for循環(huán)就是分別更新以 i 為中心且長(zhǎng)度為 2*len + 1 的奇數(shù)回文串，和以 i 為中心之一且長(zhǎng)度為 2*len + 2 的偶數(shù)回文串的。i-len 正好是奇數(shù)或者偶數(shù)回文串的起始位置，由于我們定義的 dp[i] 是區(qū)間 [0, i-1] 的最小分割數(shù)，所以 dp[i-len] 就是區(qū)間 [0, i-len-1] 范圍內(nèi)的最小分割數(shù)，那么加上奇數(shù)回文串長(zhǎng)度 2*len + 1，此時(shí)整個(gè)區(qū)間為 [0, i+len]，即需要更新 dp[i+len+1]。如果是加上偶數(shù)回文串的長(zhǎng)度 2*len + 2，那么整個(gè)區(qū)間為 [0, i+len+1]，即需要更新 dp[i+len+2]。這就是分奇偶的狀態(tài)轉(zhuǎn)移方程，參見代碼如下：

解法三：

class Solution {
public:
    int minCut(string s) {
        if (s.empty()) return 0;
        int n = s.size();
        vector<int> dp(n + 1, INT_MAX);
        dp[0] = -1;
        for (int i = 0; i < n; ++i) {
            for (int len = 0; i - len >= 0 && i + len < n && s[i - len] == s[i + len]; ++len) {
                dp[i + len + 1] = min(dp[i + len + 1], 1 + dp[i - len]);
            }
            for (int len = 0; i - len >= 0 && i + len + 1 < n && s[i - len] == s[i + len + 1]; ++len) {
                dp[i + len + 2] = min(dp[i + len + 2], 1 + dp[i - len]);
            }
        }
        return dp[n];
    }
};

到此這篇關(guān)于C++實(shí)現(xiàn)LeetCode(132.拆分回文串之二)的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)拆分回文串之二內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論