<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 {
    int memo[201][201][201];
    int fn(int idx1, int idx2, int idx, string s1, string s2, string s)
    {
        if(idx == s.length())
        {
            if(idx1 == s1.length() and idx2 == s2.length())
                return true;
            return false;
        }
        int &ans = memo[idx][idx1][idx2];
        if(ans != -1)
            return ans;
        ans = 0;            
        if(s1[idx1] == s[idx])
            ans = max(ans, fn(idx1+1, idx2, idx+1, s1, s2, s));
        if(s2[idx2] == s[idx])
            ans = max(ans, fn(idx1, idx2+1, idx+1, s1, s2, s));
        return ans;
    }
public:
    bool isInterleave(string s1, string s2, string s) {
        memset(memo, -1, sizeof(memo));
        int n1 = s1.length(), n2 = s2.length(), n3 = s.length();
        return fn(0, 0, 0, s1, s2, s);
        // int dp[n3+1][n1+1][n2+1];
        // for(int i=0; i<=n3; i++)
        //     for(int j=0; j<=n1; j++)
        //         for(int k=0; k<=n2; k++)
        //         {
        //             if(i == 0)
        //                 dp[i][j][k] = 1;
        //             else
        //                 dp[i][j][k] = 0;
        //         }
        // for(int idx=1; idx<=n3; idx++)
        // {
        //     for(int i=1; i<=n1; i++)
        //     {
        //         for(int j=1; j<=n2; j++)
        //         {
        //             if(s[idx-1] == s1[i-1])
        //                 dp[idx][i][j] = max(dp[idx][i][j], dp[idx-1][i-1][j]);
        //             if(s[idx-1] == s2[j-1])
        //                 dp[idx][i][j] = max(dp[idx][i][j], dp[idx-1][i][j-1]);
        //         }
        //     }
        // }

        // for(int idx=0; idx<=n3; idx++)
        // {
        //     cout<<idx<<endl;
        //     for(int i=1; i<=n1; i++)
        //     {
        //         for(int j=1; j<=n2; j++)
        //         {
        //             cout<<dp[idx][i][j]<<" ";
        //         }
        //         cout<<endl;
        //     }
        //     cout<<endl;
        // }

        // return dp[n3][n1][n2];
    }
};
68948