C++實(shí)現(xiàn)LeetCode(87.攪亂字符串)

更新時(shí)間：2021年07月19日 17:34:23 作者：Grandyang

這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(87.攪亂字符串),本篇文章通過簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下

[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

這道題定義了一種攪亂字符串，就是說假如把一個(gè)字符串當(dāng)做一個(gè)二叉樹的根，然后它的非空子字符串是它的子節(jié)點(diǎn)，然后交換某個(gè)子字符串的兩個(gè)子節(jié)點(diǎn)，重新爬行回去形成一個(gè)新的字符串，這個(gè)新字符串和原來的字符串互為攪亂字符串。這道題可以用遞歸 Recursion 或是動(dòng)態(tài)規(guī)劃 Dynamic Programming 來做，我們先來看遞歸的解法，簡(jiǎn)單的說，就是 s1 和 s2 是 scramble 的話，那么必然存在一個(gè)在 s1 上的長(zhǎng)度 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 當(dāng)然是 scrambled。根據(jù)這點(diǎn)，我們可以寫出代碼如下：

解法一：

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

當(dāng)然，這道題也可以用動(dòng)態(tài)規(guī)劃 Dynamic Programming，根據(jù)以往的經(jīng)驗(yàn)來說，根字符串有關(guān)的題十有八九可以用 DP 來做，那么難點(diǎn)就在于如何找出狀態(tài)轉(zhuǎn)移方程。這其實(shí)是一道三維動(dòng)態(tài)規(guī)劃的題目，使用一個(gè)三維數(shù)組 dp[i][j][n]，其中i是 s1 的起始字符，j是 s2 的起始字符，而n是當(dāng)前的字符串長(zhǎng)度，dp[i][j][len] 表示的是以i和j分別為 s1 和 s2 起點(diǎn)的長(zhǎng)度為 len 的字符串是不是互為 scramble。有了 dp 數(shù)組接下來看看狀態(tài)轉(zhuǎn)移方程，也就是怎么根據(jù)歷史信息來得到 dp[i][j][len]。判斷這個(gè)是不是滿足，首先是把當(dāng)前 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 的。而對(duì)于判斷這些左右部分是不是 scramble 是有歷史信息的，因?yàn)殚L(zhǎng)度小于n的所有情況都在前面求解過了（也就是長(zhǎng)度是最外層循環(huán)）。上面說的是劈一刀的情況，對(duì)于 s1[i...i+len-1] 有 len-1 種劈法，在這些劈法中只要有一種成立，那么兩個(gè)串就是 scramble 的。總結(jié)起來狀態(tài)轉(zhuǎn)移方程是：

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])

對(duì)于所有 1<=k<len，也就是對(duì)于所有 len-1 種劈法的結(jié)果求或運(yùn)算。因?yàn)樾畔⒍际怯?jì)算過的，對(duì)于每種劈法只需要常量操作即可完成，因此求解遞推式是需要 O(len)（因?yàn)?len-1 種劈法）。如此總時(shí)間復(fù)雜度因?yàn)槭侨S動(dòng)態(tài)規(guī)劃，需要三層循環(huán)，加上每一步需要線行時(shí)間求解遞推式，所以是 O(n^4)。雖然已經(jīng)比較高了，但是至少不是指數(shù)量級(jí)的，動(dòng)態(tài)規(guī)劃還是有很大優(yōu)勢(shì)的，空間復(fù)雜度是 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];
    }
};

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

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

下面這種解法和第一個(gè)解法思路相同，只不過沒有用排序算法，而是采用了類似于求異構(gòu)詞的方法，用一個(gè)數(shù)組來保存每個(gè)字母出現(xiàn)的次數(shù)，后面判斷 Scramble 字符串的方法和之前的沒有區(qū)別：

解法四：

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

下面這種解法實(shí)際上是解法二的遞歸形式，我們用了 memo 數(shù)組來減少了大量的運(yùn)算，注意這里的 memo 數(shù)組一定要有三種狀態(tài)，初始化為 -1，區(qū)域內(nèi)為 scramble 是1，不是 scramble 是0，這樣就避免了已經(jīng)算過了某個(gè)區(qū)間，但由于不是 scramble，從而又進(jìn)行一次計(jì)算，從而會(huì) 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;
    }
};

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

您可能感興趣的文章: