[LeetCode] 97.Interleaving String 交織相錯(cuò)的字符串

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

Example 1:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true

Example 2:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc" Output: false

這道求交織相錯(cuò)的字符串和之前那道 Word Break 的題很類(lèi)似，就像我之前說(shuō)的只要是遇到字符串的子序列或是匹配問(wèn)題直接就上動(dòng)態(tài)規(guī)劃 Dynamic Programming，其他的都不要考慮，什么遞歸呀的都是浮云（當(dāng)然帶記憶數(shù)組的遞歸寫(xiě)法除外，因?yàn)檫@也可以算是 DP 的一種），千辛萬(wàn)苦的寫(xiě)了遞歸結(jié)果拿到 OJ 上妥妥 Time Limit Exceeded，能把人氣昏了，所以還是直接就考慮 DP 解法省事些。一般來(lái)說(shuō)字符串匹配問(wèn)題都是更新一個(gè)二維 dp 數(shù)組，核心就在于找出狀態(tài)轉(zhuǎn)移方程。那么我們還是從題目中給的例子出發(fā)吧，手動(dòng)寫(xiě)出二維數(shù)組 dp 如下：

  Ø d b b c a
Ø T F F F F F
a T F F F F F
a T T T T T F
b F T T F T F
c F F T T T T
c F F F T F T

首先，這道題的大前提是字符串 s1 和 s2 的長(zhǎng)度和必須等于 s3 的長(zhǎng)度，如果不等于，肯定返回 false。那么當(dāng) s1 和 s2 是空串的時(shí)候，s3 必然是空串，則返回 true。所以直接給 dp[0][0] 賦值 true，然后若 s1 和 s2 其中的一個(gè)為空串的話，那么另一個(gè)肯定和 s3 的長(zhǎng)度相等，則按位比較，若相同且上一個(gè)位置為 True，賦 True，其余情況都賦 False，這樣的二維數(shù)組 dp 的邊緣就初始化好了。下面只需要找出狀態(tài)轉(zhuǎn)移方程來(lái)更新整個(gè)數(shù)組即可，我們發(fā)現(xiàn)，在任意非邊緣位置 dp[i][j] 時(shí)，它的左邊或上邊有可能為 True 或是 False，兩邊都可以更新過(guò)來(lái)，只要有一條路通著，那么這個(gè)點(diǎn)就可以為 True。那么我們得分別來(lái)看，如果左邊的為 True，那么我們?nèi)コ?dāng)前對(duì)應(yīng)的 s2 中的字符串 s2[j - 1] 和 s3 中對(duì)應(yīng)的位置的字符相比（計(jì)算對(duì)應(yīng)位置時(shí)還要考慮已匹配的s1中的字符），為 s3[j - 1 + i], 如果相等，則賦 True，反之賦 False。 而上邊為 True 的情況也類(lèi)似，所以可以求出狀態(tài)轉(zhuǎn)移方程為：

dp[i][j] = (dp[i - 1][j] && s1[i - 1] == s3[i - 1 + j]) || (dp[i][j - 1] && s2[j - 1] == s3[j - 1 + i]);

其中 dp[i][j] 表示的是 s2 的前 i 個(gè)字符和 s1 的前 j 個(gè)字符是否匹配 s3 的前 i+j 個(gè)字符，根據(jù)以上分析，可寫(xiě)出代碼如下：

解法一：

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        if (s1.size() + s2.size() != s3.size()) return false;
        int n1 = s1.size(), n2 = s2.size();
        vector<vector<bool>> dp(n1 + 1, vector<bool> (n2 + 1)); 
        dp[0][0] = true;
        for (int i = 1; i <= n1; ++i) {
            dp[i][0] = dp[i - 1][0] && (s1[i - 1] == s3[i - 1]);
        }
        for (int i = 1; i <= n2; ++i) {
            dp[0][i] = dp[0][i - 1] && (s2[i - 1] == s3[i - 1]);
        }
        for (int i = 1; i <= n1; ++i) {
            for (int j = 1; j <= n2; ++j) {
                dp[i][j] = (dp[i - 1][j] && s1[i - 1] == s3[i - 1 + j]) || (dp[i][j - 1] && s2[j - 1] == s3[j - 1 + i]);
            }
        }
        return dp[n1][n2];
    }
};

我們也可以把for循環(huán)合并到一起，用if條件來(lái)處理邊界情況，整體思路和上面的解法沒(méi)有太大的區(qū)別，參見(jiàn)代碼如下：

解法二：

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        if (s1.size() + s2.size() != s3.size()) return false;
        int n1 = s1.size(), n2 = s2.size();
        vector<vector<bool>> dp(n1 + 1, vector<bool> (n2 + 1, false)); 
        for (int i = 0; i <= n1; ++i) {
            for (int j = 0; j <= n2; ++j) {
                if (i == 0 && j == 0) {
                    dp[i][j] = true;
                } else if (i == 0) {
                    dp[i][j] = dp[i][j - 1] && s2[j - 1] == s3[i + j - 1];
                } else if (j == 0) {
                    dp[i][j] = dp[i - 1][j] && s1[i - 1] == s3[i + j - 1];
                } else {
                    dp[i][j] = (dp[i - 1][j] && s1[i - 1] == s3[i + j - 1]) || (dp[i][j - 1] && s2[j - 1] == s3[i + j - 1]);
                }
            }
        }
        return dp[n1][n2];
    }
};

這道題也可以使用帶優(yōu)化的 DFS 來(lái)做，我們使用一個(gè) HashSet，用來(lái)保存匹配失敗的情況，我們分別用變量i，j，和k來(lái)記錄字符串 s1，s2，和 s3 匹配到的位置，初始化的時(shí)候都傳入0。在遞歸函數(shù)中，首先根據(jù)i和j，算出 key 值，由于我們的 HashSet 中只能放一個(gè)數(shù)字，而我們要 encode 兩個(gè)數(shù)字i和j，所以通過(guò)用i乘以 s3 的長(zhǎng)度再加上j來(lái)得到 key，此時(shí)我們看，如果 key 已經(jīng)在集合中，直接返回 false，因?yàn)榧现写娴氖菬o(wú)法匹配的情況。然后先來(lái)處理 corner case 的情況，如果i等于 s1 的長(zhǎng)度了，說(shuō)明 s1 的字符都匹配完了，此時(shí) s2 剩下的字符和 s3 剩下的字符可以直接進(jìn)行匹配了，所以我們直接返回兩者是否能匹配的 bool 值。同理，如果j等于 s2 的長(zhǎng)度了，說(shuō)明 s2 的字符都匹配完了，此時(shí) s1 剩下的字符和 s3 剩下的字符可以直接進(jìn)行匹配了，所以我們直接返回兩者是否能匹配的 bool 值。如果 s1 和 s2 都有剩余字符，那么當(dāng) s1 的當(dāng)前字符等于 s3 的當(dāng)前字符，那么調(diào)用遞歸函數(shù)，注意i和k都加上1，如果遞歸函數(shù)返回 true，則當(dāng)前函數(shù)也返回 true；還有一種情況是，當(dāng) s2 的當(dāng)前字符等于 s3 的當(dāng)前字符，那么調(diào)用遞歸函數(shù)，注意j和k都加上1，如果遞歸函數(shù)返回 true，那么當(dāng)前函數(shù)也返回 true。如果匹配失敗了，則將 key 加入集合中，并返回 false 即可，參見(jiàn)代碼如下：

解法三：

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        if (s1.size() + s2.size() != s3.size()) return false;
        unordered_set<int> s;
        return helper(s1, 0, s2, 0, s3, 0, s);
    }
    bool helper(string& s1, int i, string& s2, int j, string& s3, int k, unordered_set<int>& s) {
        int key = i * s3.size() + j;
        if (s.count(key)) return false;
        if (i == s1.size()) return s2.substr(j) == s3.substr(k);
        if (j == s2.size()) return s1.substr(i) == s3.substr(k);
        if ((s1[i] == s3[k] && helper(s1, i + 1, s2, j, s3, k + 1, s)) || 
            (s2[j] == s3[k] && helper(s1, i, s2, j + 1, s3, k + 1, s))) return true;
        s.insert(key);
        return false;
    }
};

既然 DFS 可以，那么 BFS 也就坐不住了，也要出來(lái)浪一波。這里我們需要用隊(duì)列 queue 來(lái)輔助運(yùn)算，如果將解法一講解中的那個(gè)二維 dp 數(shù)組列出來(lái)的 TF 圖當(dāng)作一個(gè)迷宮的話，那么 BFS 的目的就是要從 (0, 0) 位置找一條都是T的路徑通到 (n1, n2) 位置，這里我們還要使用 HashSet，不過(guò)此時(shí)保存到是已經(jīng)遍歷過(guò)的位置，隊(duì)列中還是存 key 值，key 值的 encode 方法跟上面 DFS 解法的相同，初始時(shí)放個(gè)0進(jìn)去。然后我們進(jìn)行 while 循環(huán)，循環(huán)條件除了q不為空，還有一個(gè)是k小于 n3，因?yàn)槠ヅ渫?s3 中所有的字符就結(jié)束了。然后由于是一層層的遍歷，所以要直接循環(huán) queue 中元素個(gè)數(shù)的次數(shù)，在 for 循環(huán)中，對(duì)隊(duì)首元素進(jìn)行解碼，得到i和j值，如果i小于 n1，說(shuō)明 s1 還有剩余字符，如果 s1 當(dāng)前字符等于 s3 當(dāng)前字符，那么把 s1 的下一個(gè)位置 i+1 跟j一起加碼算出 key 值，如果該 key 值不在于集合中，則加入集合，同時(shí)加入隊(duì)列 queue 中；同理，如果j小于 n2，說(shuō)明 s2 還有剩余字符，如果 s2 當(dāng)前字符等于 s3 當(dāng)前字符，那么把 s2 的下一個(gè)位置 j+1 跟i一起加碼算出 key 值，如果該 key 值不在于集合中，則加入集合，同時(shí)加入隊(duì)列 queue 中。for 循環(huán)結(jié)束后，k自增1。最后如果匹配成功的話，那么 queue 中應(yīng)該只有一個(gè) (n1, n2) 的 key 值，且k此時(shí)等于 n3，所以當(dāng) queue 為空或者k不等于 n3 的時(shí)候都要返回 false，參見(jiàn)代碼如下：

解法四：

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        if (s1.size() + s2.size() != s3.size()) return false;
        int n1 = s1.size(), n2 = s2.size(), n3 = s3.size(), k = 0;
        unordered_set<int> s;
        queue<int> q{{0}};
        while (!q.empty() && k < n3) {
            int len = q.size();
            for (int t = 0; t < len; ++t) {
                int i = q.front() / n3, j = q.front() % n3; q.pop();
                if (i < n1 && s1[i] == s3[k]) {
                    int key = (i + 1) * n3 + j;
                    if (!s.count(key)) {
                        s.insert(key);
                        q.push(key);
                    }
                }
                if (j < n2 && s2[j] == s3[k]) {
                    int key = i * n3 + j + 1;
                    if (!s.count(key)) {
                        s.insert(key);
                        q.push(key);
                    }
                }
            }
            ++k;
        }
        return !q.empty() && k == n3;
    }
};

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

最新評(píng)論