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.

 

public bool IsInterleave(string s1, string s2, string s3) {        if(s1 == "") return s2 == s3;        if(s2 == "") return s1 == s3;        if(s1.Length + s2.Length != s3.Length) return false;        return Dp(s1,s2,s3,0,0,0);    }        private bool Dp(string s1, string s2, string s3, int i1,int i2, int i3)    {        if(i3 == s3.Length) return true;        else if(i1 >= s1.Length && i2 >= s2.Length) return false;        else        {            bool judgeS1 = false;            bool judgeS2 = false;            if(i1 

 

 

public bool IsInterleave(string s1, string s2, string s3) {        if(s1 == "") return s2 == s3;        if(s2 == "") return s1 == s3;        if(s1.Length + s2.Length != s3.Length) return false;        var dp = new bool[s1.Length+1,s2.Length+1];        dp[0,0] = true;        for(int i = 1;i<= s2.Length;i++)        {            dp[0,i] = dp[0,i-1] && (s2[i-1] == s3[i-1]);         }        for(int i = 1;i<= s1.Length;i++)        {            for(int j = 0;j<= s2.Length;j++)            {                if(j ==0) dp[i,j] = dp[i-1,j] && (s1[i-1] == s3[i-1]);                else                {                    dp[i,j] = (dp[i-1,j]&&(s1[i-1] == s3[j+i-1]))|| (dp[i,j-1]&&(s2[j-1] == s3[j+i-1]));                }            }        }        return dp[s1.Length,s2.Length];    }