题解 | #交错编号#

考察的知识点：动态规划；

解答方法分析：

1. 定义一个二维数组dp，dp[i][j]表示s1的前i个字符和s2的前j个字符能否交错组成s3的前(i+j)个字符。
2. 当s1和s2都为空字符串时，s3也必须为空字符串，因此dp[0][0] = true。当s1为空字符串时，s3[i]必须等于s2[j]，dp[0][j] = (s3[j-1] == s2[j-1]) && dp[0][j-1]，即前j个字符能否交错组成s2的前j个字符。同理，当s2为空字符串时，dp[i][0] = (s3[i-1] == s1[i-1]) && dp[i-1][0]。
3. 当s1的第i个字符和s3的第(i+j)个字符相等时，dp[i][j] = dp[i-1][j]。因为此时s1的第i个字符已经被匹配到了s3的第(i)个字符，我们只需要判断s1的前(i-1)个字符和s2的前j个字符能否交错组成s3的前(i+j-1)个字符即可。
4. 当s2的第j个字符和s的第(i+j)个字符相等时，dp[i][j] = dp[i][j-1]。
5. 最终返回结果dp[s1.size()][s2.size()]

所用编程语言：C++；

完整编程代码：↓

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s1 string字符串
     * @param s2 string字符串
     * @param s3 string字符串
     * @return bool布尔型
     */
    bool isInterleave(string s1, string s2, string s3) {
        int n1 = s1.size();
        int n2 = s2.size();
        int n3 = s3.size();
        if (n1 + n2 != n3) {
            return false;
        }
        vector<vector<bool>> dp(n1 + 1, vector<bool>(n2 + 1, false));
        dp[0][0] = true;
        for (int i = 1; i <= n1; i++) {
            if (s1[i - 1] == s3[i - 1]) {
                dp[i][0] = dp[i - 1][0];
            }
        }
        for (int j = 1; j <= n2; j++) {
            if (s2[j - 1] == s3[j - 1]) {
                dp[0][j] = dp[0][j - 1];
            }
        }
        for (int i = 1; i <= n1; i++) {
            for (int j = 1; j <= n2; j++) {
                if (s1[i - 1] == s3[i + j - 1] && dp[i - 1][j]) {
                    dp[i][j] = true;
                } else if (s2[j - 1] == s3[i + j - 1] && dp[i][j - 1]) {
                    dp[i][j] = true;
                }
            }
        }
        return dp[n1][n2];
    }
};