<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 isInterleave(const string& s1, const string& s2, const string& s3) { 
        //return isInterleaveFullMem(s1, s2, s3);
        //return isInterleaveLinearMem(s1, s2, s3);
        return isInterleaveMemo(s1, s2, s3);
    }

    bool isInterleaveFullMem(string s1, string s2, const string & s3) {
        if (s3.size() != s1.size() + s2.size()) return false;
        if (s1.size() > s2.size()) swap(s1, s2);
        //intLv[i][j] is whether the prefix of s3 of length i+j can be made by interleaving
        //the prefix of length i of s1 and the prefix of length j of s2
        vector<vector<bool>> intLv(s1.size() + 1, vector<bool>(s2.size()+1));
        intLv[0][0] = true;
        for (int i = 1; i <= s1.size(); ++i)
            intLv[i][0] = intLv[i-1][0] && s1[i-1] == s3[i-1];
        for (int j = 1; j <= s2.size(); ++j)
            intLv[0][j] = intLv[0][j-1] && s2[j-1] == s3[j-1];
        
        for (int i = 1; i <= s1.size(); ++i){
            for (int j = 1; j <= s2.size(); ++j){
                intLv[i][j] = (intLv[i-1][j] && s1[i-1] == s3[i+j-1]) || (intLv[i][j-1] && s2[j-1] == s3[i+j-1]);
            }
        }
        return intLv.back().back();
    }

    bool isInterleaveLinearMem(string s1, string s2, const string & s3) {
        if (s3.size() != s1.size() + s2.size()) return false;
        if (s1.size() < s2.size()) swap(s1, s2);
        vector<bool> intLv(s2.size()+1);
        intLv[0] = true;
        for (int i = 1; i <= s2.size(); ++i) intLv[i] = intLv[i-1] && s2[i-1] == s3[i-1];

        for (int i = 1; i <= s1.size(); ++i){
            intLv[0] = intLv[0] && s1[i-1] == s3[i-1];
            for (int j = 1; j <= s2.size(); ++j){
                intLv[j] = (intLv[j] && s1[i-1] == s3[i+j-1]) || (intLv[j-1] && s2[j-1] == s3[i+j-1]);
            }
        }
        return intLv.back();
    }

    bool isInterleaveMemo(const string & s1, const string & s2, const string & s3) {
        if (s3.size() != s1.size() + s2.size()) return false;
        unordered_map<int, bool> intLv;
        intLv[0] = true;
        return memoCompute(s1, s2, s3, s1.size(), s2.size(), intLv);
    }

    bool memoCompute(const string& s1, const string& s2, const string& s3, int i, int j, unordered_map<int, bool> & intLv) {
        if (intLv.contains(i*s2.size()+i+j)) return intLv[i*s2.size()+i+j];
        return intLv[i*s2.size()+i+j] = ((i > 0 && s1[i-1] == s3[i+j-1] && memoCompute(s1, s2, s3, i-1, j, intLv)) ||
            (j > 0 && s2[j-1] == s3[i+j-1] && memoCompute(s1, s2, s3, i, j-1, intLv)));
    }
};
11446