C++實現LeetCode(132.拆分回文串之二)

[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.

這道題是讓找到把原字符串拆分成回文串的最小切割數,如果我們首先考慮用brute force來做的話就會十分的復雜,因為我們不但要判斷子串是否是回文串,而且還要找出最小切割數,情況會非常的多,不好做。所以對於這種玩字符串且是求極值的題,就要祭出曠古神器動態規劃Dynamic Programming瞭,秒天秒地秒空氣,DP在手天下我有。好,吹完一波後,開始做題。DP解法的兩個步驟,定義dp數組和找狀態轉移方程。首先來定義dp數組,這裡使用最直接的定義方法,一維的dp數組,其中dp[i]表示子串 [0, i] 范圍內的最小分割數,那麼我們最終要返回的就是 dp[n-1] 瞭,這裡先加個corner case的判斷,若s串為空,直接返回0,OJ的test case中並沒有空串的檢測,但博主認為還是加上比較好,畢竟空串也算是回文串的一種,所以最小分割數為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] 即可,參見代碼如下:

解法一:

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數組的定義就剛好跟前面反過來瞭,dp[i] 表示區間 [i, n-1] 內的最小分割數,所以最終隻需要返回 dp[0] 就是區間 [0, n-1] 內的最喜哦啊分割數瞭,極為所求。然後每次初始化 dp[i] 為 n-1-i 即可,j 的更新范圍是 [i, n),此時我們就隻需要用 1 + dp[j+1] 來更新 dp[i] 瞭,為瞭防止越界,需要對 j == 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 = 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];
    }
};

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

解法三:

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

到此這篇關於C++實現LeetCode(132.拆分回文串之二)的文章就介紹到這瞭,更多相關C++實現拆分回文串之二內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!

推薦閱讀: