题目描述

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

算法

(动态规划) $O(m \times n)$

首先如果交错构成的，则必有s3长度等于s1和s2的长度和。另外尤其需要注意的就是顺序问题，考虑这样一个例子：

s3 = bbac
s1 = ab
s2 = bc

虽然s1和s2的字符在s3里都存在，但是违背了顺序关系。

其实这道题和编辑距离还是很接近的，用d[i][j]表示s1的前i个字符和s2的前j个字符能否和s3的前i+j个字符完成匹配。首先就是初始化问题，d[0][0]显然为true，另外初始化当s1为空和s2为空的情况。

假如s1[i - 1]和s3[i+j-1]完成匹配，那么意味着s1前i-1个和s2前j个字符要和s3前i+j-1个字符完成匹配，或者s2[j -1] == s3[i + j - 1]，则需要s1前i个和s2前j-1个匹配。两者中只要有一个满足即可，所以用或的关系。

C++ 代码

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int m = s1.size(), n = s2.size();
        if (s3.size() != m + n) return false;

        vector<vector<bool>> d(m + 1, vector<bool>(n + 1));
        d[0][0] = true;
        for (int i = 1; i <= m; ++i) {
            if (s1[i - 1] == s3[i - 1]) d[i][0] = true;
            else break;
        }

        for (int i = 1; i <= n; ++i) {
            if (s2[i - 1] == s3[i - 1]) d[0][i] = true;
            else break;
        }

        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                d[i][j] = (s1[i - 1] == s3[i + j - 1] && d[i - 1][j]) 
                    || (s2[j - 1] == s3[i + j - 1] && d[i][j - 1]);
            }
        }

        return d[m][n];
    }
};