<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 {
public:

    bool solving (int n, int m, int l, string s1, string s2, string s3, vector <vector <vector <int>>> & dp) {
        if (n == -1) {
            if (m != l) {
                return 0;
            }
            while (m >= 0) {
                if (s2[m] != s3[m]) {
                    return 0;
                }
                m--;
            }
            return 1;
        }
        if (m == -1) {
            if (n != l) {
                return 0;
            }
            while (n >= 0) {
                if (s1[n] != s3[n]) {
                    return 0;
                }
                n--;
            }
            return 1;
        }
        if (dp[n][m][l] != -1) {
            return dp[n][m][l];
        }
        if (s1[n] == s3[l] && s2[m] == s3[l]) {
            return dp[n][m][l] = solving (n-1, m, l-1, s1, s2, s3, dp) | solving (n, m-1, l-1, s1, s2, s3, dp);
        }
        else if (s1[n] == s3[l]) {
            return dp[n][m][l] = solving (n-1, m, l-1, s1, s2, s3, dp);
        }
        else if (s2[m] == s3[l]) {
            return dp[n][m][l] = solving (n, m-1, l-1, s1, s2, s3, dp);
        }
        return dp[n][m][l] = false;
    }

    bool isInterleave(string s1, string s2, string s3) {
        int n = s1.size();
        int m = s2.size();
        int l = s3.size();
        if (n+m != l) return false;
        vector <vector <vector <int>>> dp (n, vector <vector <int>> (m, vector <int> (l, -1)));
        return solving (n-1, m-1, l-1, s1, s2, s3, dp);
    }

    // bool solving (int n, int m, int l, string s1, string s2, string s3, vector <vector <int>> & dp) {
    //     if (n == -1) {
    //         if (m != l) {
    //             return 0;
    //         }
    //         while (m >= 0) {
    //             if (s2[m] != s3[m]) {
    //                 return 0;
    //             }
    //             m--;
    //         }
    //         return 1;
    //     }
    //     if (m == -1) {
    //         if (n != l) {
    //             return 0;
    //         }
    //         while (n >= 0) {
    //             if (s1[n] != s3[n]) {
    //                 return 0;
    //             }
    //             n--;
    //         }
    //         return 1;
    //     }
    //     if (dp[n][m] != -1) {
    //         return dp[n][m];
    //     }
    //     if (s1[n] == s3[l] && s2[m] == s3[l]) {
    //         return dp[n][m] = solving (n-1, m, l-1, s1, s2, s3, dp) | solving (n, m-1, l-1, s1, s2, s3, dp);
    //     }
    //     else if (s1[n] == s3[l]) {
    //         return dp[n][m] = solving (n-1, m, l-1, s1, s2, s3, dp);
    //     }
    //     else if (s2[m] == s3[l]) {
    //         return dp[n][m] = solving (n, m-1, l-1, s1, s2, s3, dp);
    //     }
    //     return dp[n][m] = false;
    // }

    // bool isInterleave(string s1, string s2, string s3) {
    //     int n = s1.size();
    //     int m = s2.size();
    //     int l = s3.size();
    //     if (n+m != l) return false;
    //     vector <vector <int>> dp (n, vector <int> (m, -1));
    //     return solving (n-1, m-1, l-1, s1, s2, s3, dp);
    // }
};
96008