https://leetcode.com/problems/interleaving-string/

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

Example 1:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true

Example 2:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output: false

不自量力开了一个hard

熬了两天

还是看题解才写出来

dp[i][j]表示的是截止这位能不能拼 不是i.j,能不能拼i+j

第一次写的dfs还超时了

class Solution {
public:
    bool dp[200][200];
    bool isInterleave(string s1, string s2, string s3) {
        int len1 = s1.length();
        int len2 = s2.length();
        if (len1 + len2 != s3.length())
            return false;
        dp[0][0] = true;
        for (int i = 0; i < len1; i ++) {
            if(s1[i] == s3[i])
                dp[i+1][0] = dp[i][0];
            else
                dp[i+1][0] = false;
        }
        for (int i = 0; i < len2; i ++) {
            if(s2[i] == s3[i])
                dp[0][i+1] = dp[0][i];
            else
                dp[0][i+1] = false;
        }
        for (int i = 1; i <= len1; i ++) {
            for (int j = 1; j <= len2; j ++) {
                bool v1 = s3[i+j-1] == s1[i-1] ? dp[i-1][j]:false;
                bool v2 = s3[i+j-1] == s2[j-1] ? dp[i][j-1]:false;
                dp[i][j] = v1 || v2;
            }
        }
        return dp[len1][len2];
    }
};