题目链接：Interleaving String

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

For example,

Given:

s1 = “aabcc”,

s2 = “dbbca”,

When s3 = “aadbbcbcac”, return true.

When s3 = “aadbbbaccc”, return false.

这道题的要求是检测字符串s3是否由s1和s2交错生成。

这是一道动态规划的题目，用dp[i, j]表示s1的前i个字符和s2的前j个字符能否通过交错生成s3的前i+j个字符。

至于dp数组的初值，当j等于0的时候，dp[i, 0]的值取决于dp[i-1, 0]是否为真以及s1[i-1]是否等于s3[i-1]，即

  • dp[i][0] = dp[i-1][0] && s1[i-1] == s3[i-1]

同理，当i等于0的时候：

  • dp[0][j] = dp[0][j-1] && s2[j-1] == s3[j-1]

至于递推公式，取决于当期读到的字符是否等于s3中对应的字符相同：

  • 如果s1[i-1]与s3[i+j-1]相同，说明当前位置s1可以进行匹配，因此如果dp[i-1, j]也为真，dp[i, j]就为真。
  • 如果s2[j-1]与s3[i+j-1]相同，说明当前位置s2可以进行匹配，因此如果dp[i, j-1]也为真，dp[i, j]就为真。
综上所述，递推公式为dp[i, j] = (s1[i-1] == s3[i+j-1] && dp[i-1, j])   (s2[j-1] == s3[i+j-1] && dp[i, j-1])。

注意一下，如果s1的长度加上s2的长度不等于s3的长度，则直接返回false即可。

时间复杂度：O(nm)

空间复杂度：O(nm)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution
{
public:
    bool isInterleave(string s1, string s2, string s3)
    {
        int l1 = s1.size(), l2 = s2.size(), l3 = s3.size();

        if(l3 != l1 + l2)
            return false;

        vector<vector<bool> > dp(l1 + 1, vector<bool>(l2 + 1, false));

        dp[0][0] = true;
        for(int i = 1; i <= l1; ++ i)
            dp[i][0] = dp[i - 1][0] && s1[i - 1] == s3[i - 1];
        for(int j = 1; j <= l2; ++ j)
            dp[0][j] = dp[0][j - 1] && s2[j - 1] == s3[j - 1];

        for(int i = 1; i <= l1; ++ i)
            for(int j = 1; j <= l2; ++ j)
                dp[i][j] = (s1[i - 1] == s3[i + j - 1] && dp[i - 1][j]) 
                        || (s2[j - 1] == s3[i + j - 1] && dp[i][j - 1]);

        return dp[l1][l2];
    }
};

这道题还有人给出了BFS的方法。