LeetCode 97. Interleaving String [Hard] [C++] 解題筆記

這題給定三個字串 s1 , s2 , s3，要我們判斷 s3 是否可由 s1, s2 "交錯" 組合出來。

EX:

        s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"

        Ans: True

想法:

        基本上遇到字串匹配或是子字串，子序列之類的就是直接 DP 了拉！！

這題也一樣，我們可以假設 dp[i][j] 表示 s1[0:i-1] 長度為 i , s2[0:j-1] 長度為 j 時可否交錯組合出 s3[0:i+j-1] (長度為 i + j)，首先 s1 長度 + s2 長度不等於 s3 長度時一定不匹配，而 s1, s2 , s3 長度皆為 0 時一定匹配，有了base case 之後就可以照著下列轉移方程來找到解:

                            // 表示 s1 的第 i 個字元可以與 s3 的第 i + j 個字元匹配

            dp[i][j] = dp[i - 1][j] && s1[i - 1] == s3[i + j - 1] || 

                            // 表示 s2 的第 j 個字元可以與 s3 的第 i + j 個字元匹配

                            dp[i][j - 1] && s2[j - 1] == s3[i + j - 1]

另外 DP 通常可以轉換成 DFS + memorization 的方式來實作，基本上概念是一樣的，只是改成 recursive 的方式而已。(單純 DFS run time 會過久)

Complexity: O(m*n) time, O(m*n) space. m is length of s1, n is length of s2.

完整程式碼:

解法一(DP):

class Solution {

public:

    bool isInterleave(string s1, string s2, string s3) {

        if (s1.size() + s2.size() != s3.size()) { return false; }

        // dp[i][j] means that if s1[0:i-1] and s2[0:j-1] can form s2[0:i + j - 1] or not 

        vector<vector<bool>> dp(s1.size() + 1, vector<int>(s2.size() + 1, false));

        dp[0][0] = true;

        for (int i = 1; i <= s1.size(); i++) {

            dp[i][0] = (dp[i - 1][0] && s1[i - 1] == s3[i - 1]);

        }

        for (int j = 1; j <= s2.size(); j++) {

            dp[0][j] = (dp[0][j - 1] && s2[j - 1] == s3[j - 1]);

        }

        for (int i = 1; i <= s1.size(); i++) {

            for (int j = 1; j <= s2.size(); j++) {

                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[s1.size()][s2.size()];

    }

};

解法二(DFS without memorization, TLE):

class Solution {

public:

    bool dfs(string_view s1, string_view s2, string_view s3) {

        if (s1.size() + s2.size() != s3.size()) { return false; }

        if (s3.empty()) { return true; }

        if (s1.empty()) {

            return  s2.back() == s3.back() && dfs(s1, s2.substr(0, s2.size() - 1), s3.substr(0, s2.size() - 1));

        }

        if (s2.empty()) {

            return s1.back() == s3.back() && dfs(s1.substr(0, s1.size() - 1), s2, s3.substr(0, s1.size() - 1));

        }

        return (s1.back() == s3.back() && dfs(s1.substr(0, s1.size() - 1), s2, s3.substr(0, s1.size() + s2.size() - 1))) || (s2.back() == s3.back() && dfs(s1, s2.substr(0, s2.size() - 1), s3.substr(0, s1.size() + s2.size() - 1)));

    }

    bool isInterleave(string s1, string s2, string s3) {

        return dfs(s1, s2, s3);

    }

};

解法三(DFS with memorization):

class Solution {

public:

    bool dfs(string_view s1, string_view s2, string_view s3) {

        if (s1.size() + s2.size() != s3.size()) { return false; }

        if (s1.empty() && s2.empty()) { return true; }

        if (dp[s1.size()][s2.size()] != INT_MIN) { return dp[s1.size()][s2.size()]; }

        if ((!s2.empty() && s2.back() == s3.back() && dfs(s1, s2.substr(0, s2.size() - 1), s3.substr(0, s1.size() + s2.size() - 1)))

            || 

            (!s1.empty() && s1.back() == s3.back() && dfs(s1.substr(0, s1.size() - 1), s2, s3.substr(0, s1.size() + s2.size() - 1)))) {

            dp[s1.size()][s2.size()] = 1;

        }

        else {

            dp[s1.size()][s2.size()] = 0;

        }

        return dp[s1.size()][s2.size()];

    }

    bool isInterleave(string s1, string s2, string s3) {

        dp = vector<vector<int>>(s1.size() + 1, vector<int>(s2.size() + 1, INT_MIN));

        return dfs(s1, s2, s3);

    }

private:

    vector<vector<int>> dp;

};