1、思路

• 字符串s1与s2的长度之和必须等于s3，否则无法交织；

• dp[i][j]表示字符串s1[0 ... i - 1]与字符串s2[0 ... j - 1]能够交织成字符串s3[0 ... i + j - 1]；

• 状态初始化：
  1、首先dp[0][0] = 0，表示两个空字符串能交织成一个空字符串；
  2、dp[i][0]与dp[0][j]表示其中一个字符串为空时，另一个字符串能否交织出s3；

• dp[i][j]的值依赖于dp[i - 1][j]和dp[i][j - 1]：
  1、当s3[i + j - 1]与s1[i - 1]相同时，dp[i][j]的值等于dp[i - 1][j]的值；
  2、当s3[i + j - 1]与s2[j - 1]相同时，dp[i][j]的值等于dp[i][j - 1]的值。

2、代码

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        if (s1.length() + s2.length() != s3.length()) return false;

        vector<vector<bool>> dp(s1.length() + 1, vector<bool>(s2.length() + 1, false));
        dp[0][0] = true;

        for (int i = 1; i <= s1.length(); ++ i)
        {   //当s2为空时，判断s1能否交织出s3
            dp[i][0] = s1[i - 1] == s3[i - 1] && dp[i - 1][0];
        }

        for (int j = 1; j <= s2.length(); ++ j)
        {   //当s1为空时，判断s2能否交织出s3
            dp[0][j] = s2[j - 1] == s3[j - 1] && dp[0][j - 1];
        }

        for (int i = 1; i <= s1.length(); ++ i)
        {
            for (int j = 1; j <= s2.length(); ++ j)
            {
                char ch1 = s1[i - 1], ch2 = s2[j - 1], ch3 = s3[i + j - 1];
                dp[i][j] = (ch1 == ch3 && dp[i - 1][j]) || (ch2 == ch3 && dp[i][j - 1]);
            }
        }

        return dp[s1.length()][s2.length()];
    }
};