# 97-interleaving-string


Try it on <a href='https://leetcode.com/problems/97-interleaving-string'>leetcode</a>

## Description
<div class="description">
<div><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 they are divided into <strong>non-empty</strong> substrings 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>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 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
<strong>Output:</strong> true
</pre>

<p><strong>Example 2:</strong></p>

<pre><strong>Input:</strong> s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
<strong>Output:</strong> false
</pre>

<p><strong>Example 3:</strong></p>

<pre><strong>Input:</strong> s1 = "", s2 = "", s3 = ""
<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>
</div>
</div>

## Solution(Python)
```Python
class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        return self.memoize(s1, s2, s3)
        
    # Time Complexity: O(2^(m+n))
    # space Complexity: O(m+n)
    def bruteforce(self, s1: str, s2: str, s3: str) -> bool:
        def dfs(s1,i,s2,j,res,s3):
            if res == s3 and i == len(s1) and j == len(s2):
                return True
            ans = False
            if i < len(s1):
                ans |= dfs(s1,i+1,s2,j,res+s1[i],s3)
            if j < len(s2):
                ans |= dfs(s1,i,s2,j+1,res+s2[j],s3)
            return ans
        
        if len(s1) + len(s2) != len(s3):
            return False
        
        return dfs(s1,0,s2,0,"",s3)
    
    # Time Complexity: O(m*n)
    # space Complexity: O(m*n)
    def memoize(self, s1: str, s2: str, s3: str) -> bool:
        if len(s1) + len(s2) != len(s3):
            return False
        
        dp = [[0 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 and j == 0:
                    dp[i][j] = True
                elif i == 0:
                    dp[i][j] = dp[i][j-1] and s2[j-1] == s3[i+j-1] 
                elif j == 0:
                    dp[i][j] = dp[i-1][j] and s1[i-1] == s3[i+j-1] 
                else:
                    dp[i][j] = ( dp[i][j-1] and s2[j-1] == s3[i+j-1] ) or (dp[i-1][j] and s1[i-1] == s3[i+j-1] )
        
        return dp[-1][-1]
        
```