<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:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        # 1. Recursive backtracking approach
        # if (len(s1) + len(s2)) != len(s3):
        #     return False
        # def is_interleaved(i, j):
        #     # Base case:
        #     if i < 0 and j >= 0:
        #         return s3[0:j+1] == s2[0:j+1]
        #     elif j < 0 and i >= 0:
        #         return s3[0:i+1] == s1[0:i+1]
        #     elif i < 0 and j < 0:
        #         return True
        #     # Explore all possibilities
        #     s1_match = s3[i+j+1] == s1[i] and is_interleaved(i-1, j)
        #     s2_match = s3[i+j+1] == s2[j] and is_interleaved(i, j-1)
        #     # Return best result
        #     return s1_match or s2_match

        # return is_interleaved(len(s1)-1, len(s2)-1)

        # 2. Top down dynamic programming
        # if (len(s1) + len(s2)) != len(s3):
        #     return False
        # def is_interleaved(i, j, memo):
        #     if i < 0 and j >= 0:
        #         return s3[0:j+1] == s2[0:j+1]
        #     elif j < 0 and i >= 0:
        #         return s3[0:i+1] == s1[0:i+1]
        #     elif i < 0 and j < 0:
        #         return True

        #     if memo[i][j]:
        #         return memo[i][j]
        #     s1_match = s3[i+j+1] == s1[i] and is_interleaved(i-1, j, memo)
        #     s2_match = s3[i+j+1] == s2[j] and is_interleaved(i, j-1, memo)
        #     memo[i][j] = s1_match or s2_match
        #     return memo[i][j]
        # memo = [[None for _ in range(len(s2) + 1)] for _ in range(len(s1) + 1)]
        # return is_interleaved(len(s1)-1, len(s2)-1, memo)

        # 3. Bottom up dynamic programming
        # if (len(s1) + len(s2)) != len(s3):
        #     return False
        # memo = [[False for _ in range(len(s2) + 1)] for _ in range(len(s1) + 1)]
        # for i in range(len(s1) + 1):
        #     for j in range(len(s2) + 1):
        #         if i == 0 or j == 0:
        #             if i == 0 and j > 0:
        #                 memo[i][j] = s3[0:j] == s2[0:j]
        #             elif j == 0 and i > 0:
        #                 memo[i][j] = s3[0:i] == s1[0:i]
        #             elif i == 0 and j == 0:
        #                 memo[i][j] = True
        #         else:             
        #             s1_match = s3[i+j-1] == s1[i-1] and memo[i-1][j]   
        #             s2_match = s3[i+j-1] == s2[j-1] and memo[i][j-1]
        #             memo[i][j] = s1_match or s2_match
        # return memo[len(s1)][len(s2)]
        
        # 4. Space optimized Bottom up dynamic programming
        if (len(s1) + len(s2)) != len(s3):
            return False
        prev = [False for _ in range(len(s2) + 1)]
        for i in range(len(s1) + 1):
            current = [False for _ in range(len(s2) + 1)]
            for j in range(len(s2) + 1):
                if i == 0 or j == 0:
                    if i == 0 and j > 0:
                        current[j] = s3[0:j] == s2[0:j]
                    elif j == 0 and i > 0:
                        current[j] = s3[0:i] == s1[0:i]
                    elif i == 0 and j == 0:
                        current[j] = True
                else:             
                    s1_match = s3[i+j-1] == s1[i-1] and prev[j]
                    s2_match = s3[i+j-1] == s2[j-1] and current[j-1]
                    current[j] = s1_match or s2_match
            prev = current
        return prev[len(s2)]
        
16400