https://leetcode.cn/problems/interleaving-string/submissions/578139088/
给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的。

两个字符串 s 和 t 交错 的定义与过程如下，其中每个字符串都会被分割成若干 非空
子字符串
：

s = s1 + s2 + … + sn
t = t1 + t2 + … + tm
|n - m| <= 1
交错 是 s1 + t1 + s2 + t2 + s3 + t3 + … 或者 t1 + s1 + t2 + s2 + t3 + s3 + …
注意：a + b 意味着字符串 a 和 b 连接。

本题并不能用双指针做，例如s1:aaaa,s2:aabc,s3:aabcaaaa,如果遇到相同的如果选错的话就都错了，我们定义dp[i][j]为bool数组，如果s1的前i个字符和s2的前j个字符能组成s3的前i+j个字符，就true，前提是长度s2+s2=s3，如果可以组成，最后一个字符要不是s1和s3相等，就是s2和s3相等，如果是前者，看看dp[i-1][j]等不等于true，如果是后者，看看dp[i][j-1]等不等于true，满足其一就可以dp[i][j]=true

const int N=110;
int dp[N][N];

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int n=s1.length();
        int m=s2.length();
        int k=s3.length();
        s1=" "+s1;
        s2=" "+s2;
        s3=" "+s3;
        for(int i=0;i<=n;i++)
            for(int j=0;j<=m;j++)
                dp[i][j]=0;


        if(n+m!=k) return false;
        dp[0][0]=1;
        for(int i=1;i<=n;i++) 
        {
            if(s1[i]==s3[i]) dp[i][0]=1;
            else break;
        }
        for(int i=1;i<=m;i++)
        {
            if(s2[i]==s3[i]) dp[0][i]=1;
            else break;
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                if(s1[i]==s3[i+j]&&dp[i-1][j]==1) dp[i][j]=1;
                if(s2[j]==s3[i+j]&&dp[i][j-1]==1) dp[i][j]=1;
            }
        }
        if(dp[n][m]==1) return true;
        else return false;
    }
};

const int N=110;
int dp[N];

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int n=s1.length();
        int m=s2.length();
        int k=s3.length();
        s1=" "+s1;
        s2=" "+s2;
        s3=" "+s3;
        for(int i=0;i<=m;i++) dp[i]=0;
        if(n+m!=k) return false;
        dp[0]=1;
        /*  for(int i=1;i<=n;i++) 
        {
            if(s1[i]==s3[i]) dp[i][0]=1;
            else break;
        }
        for(int i=1;i<=m;i++)
        {
            if(s2[i]==s3[i]) dp[0][i]=1;
            else break;
        }*/
        for(int i=1;i<=m;i++) 
        {
            if(s2[i]==s3[i]) dp[i]=1;
            else break;
        }
        int len=0;
        for(int i=1;i<=n;i++)
        {
            if(s1[i]==s3[i]) len++;
            else break;
        }
        for(int i=1;i<=n;i++)
        {
           if(i<=len) dp[0]=1;
           else dp[0]=0;
           for(int j=1;j<=m;j++)
           {
                if(s1[i]==s3[i+j]&&dp[j]==1||s2[j]==s3[j+i]&&dp[j-1]==1) dp[j]=1;
                else dp[j]=0;
           }
        }
        if(dp[m]==1) return true;
        else return false;
    }
};