C++實現LeetCode(87.攪亂字符串)

Posted on by

[LeetCode] 87. Scramble String 攪亂字符串

Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.

Below is one possible representation of s1 = ”great”:

    great
/    \
gr    eat
/ \    /  \
g   r  e   at
/ \
a   t

To scramble the string, we may choose any non-leaf node and swap its two children.

For example, if we choose the node ”gr” and swap its two children, it produces a scrambled string ”rgeat”.

    rgeat
/    \
rg    eat
/ \    /  \
r   g  e   at
/ \
a   t

We say that ”rgeat” is a scrambled string of ”great”.

Similarly, if we continue to swap the children of nodes ”eat” and ”at”, it produces a scrambled string ”rgtae”.

    rgtae
/    \
rg    tae
/ \    /  \
r   g  ta  e
/ \
t   a

We say that ”rgtae” is a scrambled string of ”great”.

Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.

Example 1:

Input: s1 = “great”, s2 = “rgeat”
Output: true

Example 2:

Input: s1 = “abcde”, s2 = “caebd”
Output: false

這道題定義瞭一種攪亂字符串，就是說假如把一個字符串當做一個二叉樹的根，然後它的非空子字符串是它的子節點，然後交換某個子字符串的兩個子節點，重新爬行回去形成一個新的字符串，這個新字符串和原來的字符串互為攪亂字符串。這道題可以用遞歸 Recursion 或是動態規劃 Dynamic Programming 來做，我們先來看遞歸的解法，簡單的說，就是 s1 和 s2 是 scramble 的話，那麼必然存在一個在 s1 上的長度 l1，將 s1 分成 s11 和 s12 兩段，同樣有 s21 和 s22，那麼要麼 s11 和 s21 是 scramble 的並且 s12 和 s22 是 scramble 的；要麼 s11 和 s22 是 scramble 的並且 s12 和 s21 是 scramble 的。就拿題目中的例子 rgeat 和 great 來說，rgeat 可分成 rg 和 eat 兩段， great 可分成 gr 和 eat 兩段，rg 和 gr 是 scrambled 的， eat 和 eat 當然是 scrambled。根據這點，我們可以寫出代碼如下：

解法一：

// Recursion
class Solution {
public:
    bool isScramble(string s1, string s2) {
        if (s1.size() != s2.size()) return false;
        if (s1 == s2) return true;
        string str1 = s1, str2 = s2;
        sort(str1.begin(), str1.end());
        sort(str2.begin(), str2.end());
        if (str1 != str2) return false;
        for (int i = 1; i < s1.size(); ++i) {
            string s11 = s1.substr(0, i);
            string s12 = s1.substr(i);
            string s21 = s2.substr(0, i);
            string s22 = s2.substr(i);
            if (isScramble(s11, s21) && isScramble(s12, s22)) return true;
            s21 = s2.substr(s1.size() - i);
            s22 = s2.substr(0, s1.size() - i);
            if (isScramble(s11, s21) && isScramble(s12, s22)) return true;
        }
        return false;
    }
};

當然，這道題也可以用動態規劃 Dynamic Programming，根據以往的經驗來說，根字符串有關的題十有八九可以用 DP 來做，那麼難點就在於如何找出狀態轉移方程。這其實是一道三維動態規劃的題目，使用一個三維數組 dp[i][j][n]，其中i是 s1 的起始字符，j是 s2 的起始字符，而n是當前的字符串長度，dp[i][j][len] 表示的是以i和j分別為 s1 和 s2 起點的長度為 len 的字符串是不是互為 scramble。有瞭 dp 數組接下來看看狀態轉移方程，也就是怎麼根據歷史信息來得到 dp[i][j][len]。判斷這個是不是滿足，首先是把當前 s1[i…i+len-1] 字符串劈一刀分成兩部分，然後分兩種情況：第一種是左邊和 s2[j…j+len-1] 左邊部分是不是 scramble，以及右邊和 s2[j…j+len-1] 右邊部分是不是 scramble；第二種情況是左邊和 s2[j…j+len-1] 右邊部分是不是 scramble，以及右邊和 s2[j…j+len-1] 左邊部分是不是 scramble。如果以上兩種情況有一種成立，說明 s1[i…i+len-1] 和 s2[j…j+len-1] 是 scramble 的。而對於判斷這些左右部分是不是 scramble 是有歷史信息的，因為長度小於n的所有情況都在前面求解過瞭（也就是長度是最外層循環）。上面說的是劈一刀的情況，對於 s1[i…i+len-1] 有 len-1 種劈法，在這些劈法中隻要有一種成立，那麼兩個串就是 scramble 的。總結起來狀態轉移方程是：

dp[i][j][len] = || (dp[i][j][k] && dp[i+k][j+k][len-k] || dp[i][j+len-k][k] && dp[i+k][j][len-k])

對於所有 1<=k<len，也就是對於所有 len-1 種劈法的結果求或運算。因為信息都是計算過的，對於每種劈法隻需要常量操作即可完成，因此求解遞推式是需要 O(len)（因為 len-1 種劈法）。如此總時間復雜度因為是三維動態規劃，需要三層循環，加上每一步需要線行時間求解遞推式，所以是 O(n^4)。雖然已經比較高瞭，但是至少不是指數量級的，動態規劃還是有很大優勢的，空間復雜度是 O(n^3)。代碼如下：

解法二：

// DP
class Solution {
public:
    bool isScramble(string s1, string s2) {
        if (s1.size() != s2.size()) return false;
        if (s1 == s2) return true;
        int n = s1.size();
        vector<vector<vector<bool>>> dp (n, vector<vector<bool>>(n, vector<bool>(n + 1)));
        for (int len = 1; len <= n; ++len) {
            for (int i = 0; i <= n - len; ++i) {
                for (int j = 0; j <= n - len; ++j) {
                    if (len == 1) {
                        dp[i][j][1] = s1[i] == s2[j];
                    } else {
                        for (int k = 1; k < len; ++k) {
                            if ((dp[i][j][k] && dp[i + k][j + k][len - k]) || (dp[i + k][j][len - k] && dp[i][j + len - k][k])) {
                                dp[i][j][len] = true;
                            }
                        }
                    }                
                }
            }
        }
        return dp[0][0][n];
    }
};

上面的代碼的實現過程如下，首先按單個字符比較，判斷它們之間是否是 scrambled 的。在更新第二個表中第一個值 (gr 和 rg 是否為 scrambled 的)時，比較瞭第一個表中的兩種構成，一種是 g與r, r與g，另一種是 g與g, r與r，其中後者是真，隻要其中一個為真，則將該值賦真。其實這個原理和之前遞歸的原理很像，在判斷某兩個字符串是否為 scrambled 時，比較它們所有可能的拆分方法的子字符串是否是 scrambled 的，隻要有一個種拆分方法為真，則比較的兩個字符串一定是 scrambled 的。比較 rge 和 gre 的實現過程如下所示：

     r    g    e
g    x    √    x
r    √    x    x
e    x    x    √

rg    ge
gr    √    x
re    x    x

rge
gre   √

DP 的另一種寫法，思路都一樣，代碼如下：

解法三：

// Still DP
class Solution {
public:
    bool isScramble(string s1, string s2) {
        if (s1.size() != s2.size()) return false;
        if (s1 == s2) return true;
        int n = s1.size();
        vector<vector<vector<bool>>> dp (n, vector<vector<bool>>(n, vector<bool>(n + 1)));
        for (int i = n - 1; i >= 0; --i) {
            for (int j = n - 1; j >= 0; --j) {
                for (int k = 1; k <= n - max(i, j); ++k) {
                    if (s1.substr(i, k) == s2.substr(j, k)) {
                        dp[i][j][k] = true;
                    } else {
                        for (int t = 1; t < k; ++t) {
                            if ((dp[i][j][t] && dp[i + t][j + t][k - t]) || (dp[i][j + k - t][t] && dp[i + t][j][k - t])) {
                                dp[i][j][k] = true;
                                break;
                            }
                        }
                    }
                }
            }
        }
        return dp[0][0][n];
    }
};

下面這種解法和第一個解法思路相同，隻不過沒有用排序算法，而是采用瞭類似於求異構詞的方法，用一個數組來保存每個字母出現的次數，後面判斷 Scramble 字符串的方法和之前的沒有區別：

解法四：

class Solution {
public:
    bool isScramble(string s1, string s2) {
        if (s1 == s2) return true;
        if (s1.size() != s2.size()) return false;
        int n = s1.size(), m[26] = {0};
        for (int i = 0; i < n; ++i) {
            ++m[s1[i] - 'a'];
            --m[s2[i] - 'a'];
        }
        for (int i = 0; i < 26; ++i) {
            if (m[i] != 0) return false;
        }
        for (int i = 1; i < n; ++i) {
            if ((isScramble(s1.substr(0, i), s2.substr(0, i)) && isScramble(s1.substr(i), s2.substr(i))) || (isScramble(s1.substr(0, i), s2.substr(n - i)) && isScramble(s1.substr(i), s2.substr(0, n - i)))) {
                return true;
            }
        }
        return false;
    }
};

下面這種解法實際上是解法二的遞歸形式，我們用瞭 memo 數組來減少瞭大量的運算，註意這裡的 memo 數組一定要有三種狀態，初始化為 -1，區域內為 scramble 是1，不是 scramble 是0，這樣就避免瞭已經算過瞭某個區間，但由於不是 scramble，從而又進行一次計算，從而會 TLE，參見代碼如下：

解法五：

class Solution {
public:
    bool isScramble(string s1, string s2) {
        if (s1 == s2) return true;
        if (s1.size() != s2.size()) return false;
        int n = s1.size();
        vector<vector<vector<int>>> memo(n, vector<vector<int>>(n, vector<int>(n + 1, -1)));
        return helper(s1, s2, 0, 0, n, memo);
    }
    bool helper(string& s1, string& s2, int idx1, int idx2, int len, vector<vector<vector<int>>>& memo) {
        if (len == 0) return true;
        if (len == 1) memo[idx1][idx2][len] = s1[idx1] == s2[idx2];
        if (memo[idx1][idx2][len] != -1) return memo[idx1][idx2][len];
        for (int k = 1; k < len; ++k) {
            if ((helper(s1, s2, idx1, idx2, k, memo) && helper(s1, s2, idx1 + k, idx2 + k, len - k, memo)) || (helper(s1, s2, idx1, idx2 + len - k, k, memo) && helper(s1, s2, idx1 + k, idx2, len - k, memo))) {
                return memo[idx1][idx2][len] = 1;
            }
        }
        return memo[idx1][idx2][len] = 0;
    }
};

到此這篇關於C++實現LeetCode(87.攪亂字符串)的文章就介紹到這瞭,更多相關C++實現攪亂字符串內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：