<p>Given strings <code>s1</code>, <code>s2</code>, and <code>s3</code>, find whether <code>s3</code> is formed by an <strong>interleaving</strong> of <code>s1</code> and <code>s2</code>.</p>

<p>An <strong>interleaving</strong> of two strings <code>s</code> and <code>t</code> is a configuration where <code>s</code> and <code>t</code> are divided into <code>n</code> and <code>m</code> <span data-keyword="substring-nonempty">substrings</span> respectively, such that:</p>

<ul>
	<li><code>s = s<sub>1</sub> + s<sub>2</sub> + ... + s<sub>n</sub></code></li>
	<li><code>t = t<sub>1</sub> + t<sub>2</sub> + ... + t<sub>m</sub></code></li>
	<li><code>|n - m| &lt;= 1</code></li>
	<li>The <strong>interleaving</strong> is <code>s<sub>1</sub> + t<sub>1</sub> + s<sub>2</sub> + t<sub>2</sub> + s<sub>3</sub> + t<sub>3</sub> + ...</code> or <code>t<sub>1</sub> + s<sub>1</sub> + t<sub>2</sub> + s<sub>2</sub> + t<sub>3</sub> + s<sub>3</sub> + ...</code></li>
</ul>

<p><strong>Note:</strong> <code>a + b</code> is the concatenation of strings <code>a</code> and <code>b</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/09/02/interleave.jpg" style="width: 561px; height: 203px;" />
<pre>
<strong>Input:</strong> s1 = &quot;aabcc&quot;, s2 = &quot;dbbca&quot;, s3 = &quot;aadbbcbcac&quot;
<strong>Output:</strong> true
<strong>Explanation:</strong> One way to obtain s3 is:
Split s1 into s1 = &quot;aa&quot; + &quot;bc&quot; + &quot;c&quot;, and s2 into s2 = &quot;dbbc&quot; + &quot;a&quot;.
Interleaving the two splits, we get &quot;aa&quot; + &quot;dbbc&quot; + &quot;bc&quot; + &quot;a&quot; + &quot;c&quot; = &quot;aadbbcbcac&quot;.
Since s3 can be obtained by interleaving s1 and s2, we return true.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s1 = &quot;aabcc&quot;, s2 = &quot;dbbca&quot;, s3 = &quot;aadbbbaccc&quot;
<strong>Output:</strong> false
<strong>Explanation:</strong> Notice how it is impossible to interleave s2 with any other string to obtain s3.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> s1 = &quot;&quot;, s2 = &quot;&quot;, s3 = &quot;&quot;
<strong>Output:</strong> true
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>0 &lt;= s1.length, s2.length &lt;= 100</code></li>
	<li><code>0 &lt;= s3.length &lt;= 200</code></li>
	<li><code>s1</code>, <code>s2</code>, and <code>s3</code> consist of lowercase English letters.</li>
</ul>

<p>&nbsp;</p>
<p><strong>Follow up:</strong> Could you solve it using only <code>O(s2.length)</code> additional memory space?</p>

class Solution {
    bool isInterleave(string s1,int b1,string s2,int b2,string s3,int b3,bool isFirst){
        if(!isFirst){
            std::swap(s1,s2);
            std::swap(b1,b2);
        }     
        int sz1 = s1.length(),sz2 = s2.length(),sz3 = s3.length();
        if(b1 == sz1 && b2 == sz2 && b3 == sz3){
            return true;
        }
                
        for(int i=sz2-b2;i>=1;i--){
            if(s1.substr(b1,i) == s3.substr(b3,i)         
                && isInterleave(s1,b1+i,s2,b2,s3,b3+i,false)){
                    return true;
                }
        }
        return false;
    }
public:
/*  //time limit exceeded
    bool isInterleave(string s1, string s2, string s3) {
        // dp[i] = dp[i-l]       
        return isInterleave(s1,0,s2,0,s3,0,true)||isInterleave(s1,0,s2,0,s3,0,false);
    }
*/
    bool isInterleave(string s1, string s2, string s3) {
        //dp[i][j] = true, if dp[i][j-l]&&s2[j-l:j]==s3[i+j+1-l:i+j+1],dp[i-l][j]&&...
                
        int sz1 = s1.length(),sz2 = s2.length(),sz3 = s3.length();
        if(sz1+sz2!=sz3){
            return false;
        }
        std::vector<std::vector<bool>> dp(sz1+1,std::vector<bool>(sz2+1,false));
        dp[0][0] = true;
        for(int i = 1;i<=sz1 && s1[i-1] == s3[i-1];i++){        
            dp[i][0] = dp[i-1][0];
        }
        for(int j = 1;j<=sz2 && s2[j-1] == s3[j-1];j++){            
            dp[0][j] = dp[0][j-1];
        }
        for(int i = 1;i<=sz1;i++){
            for(int j = 1;j<=sz2;j++){
                for(int k = 1;k<=i && dp[i][j]==false;k++){
                    dp[i][j] = dp[i-k][j] && s1.substr(i-k,k)==s3.substr(i+j-k,k);
                }
                for(int k = 1;k<=j && dp[i][j]==false;k++){
                    dp[i][j] = dp[i][j-k] && s2.substr(j-k,k)==s3.substr(i+j-k,k);
                }
            }
        }
        // for(auto rs:dp){
        //     for(auto v:rs){
        //         std::cout << v<<"\t";
        //     }
        //     std::cout <<"\n";
        // }
        return dp[sz1][sz2];
    }    
};
73458