<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:
        """
        - At each idx, if both match, can add one or the other

        DFS w/cache:
        - If len(s1) + len(s2) != s3, return False
        - Init cache
        - DFS helper taking s1_idx (i), s2_idx (j), s3_idx (k)
            - if s3_idx == len(s3): return True
            - Elif s1_idx == len(s1): 
                - If s2[s2_idx] == s3[s3_idx], 
                    - cache[(i,j)] = increment s2_idx and call DFS
                - else, return False
            - Elif s2_idx == len(s2):
                - If s1[s1_idx] == s3[s3_idx]
                    - cache[(i,j)] = increment s1_idx and call DFS
                - else, return False
            - if s1[i] == s1[j] == s3[k], 
                - cache[(i,j)] = dfs(inc i) OR dfs(inc j)
            - Each individually
            - return cache[(i,j)]
        """
        if len(s1) + len(s2) != len(s3):
            return False

        cache: dict[tuple[int,int], bool] = {}

        def dfs(i: int, j: int, k: int):
            tup = (i,j)
            if k == len(s3):
                return True
            elif tup in cache:
                return cache[tup]
            
            if i == len(s1):
                cache[tup] = dfs(i, j+1, k+1) if s2[j] == s3[k] else False
            elif j == len(s2):
                cache[tup] = dfs(i+1, j, k+1) if s1[i] == s3[k] else False
            elif s1[i] == s2[j] and s1[i] == s3[k]:
                cache[tup] = dfs(i, j+1, k+1) or dfs(i+1, j, k+1)
            elif s1[i] == s3[k]:
                cache[tup] = dfs(i+1, j, k+1)
            elif s2[j] == s3[k]:
                cache[tup] = dfs(i, j+1, k+1)
            else:
                cache[tup] = False

            return cache[tup]

        return dfs(0,0,0)





























































    def isInterleaveOld(self, s1: str, s2: str, s3: str) -> bool:
        if len(s1) + len(s2) != len(s3):
            return False

        prior_row = [False for _ in range(len(s2) + 1)]

        for i in range(len(s1) + 1):
            curr_row = [False for _ in range(len(s2) + 1)]
            for j in range(len(s2) + 1):
                if i == 0 and j == 0:
                    prior_row[0] = True
                    curr_row[0] = True
                    continue
                
                s3_char = s3[i + j - 1]
                if i == 0:
                    # checking if s2 matches to this point
                    curr_row[j] = curr_row[j - 1] and s2[j - 1] == s3_char
                elif j == 0:
                    # check if s1 matches to this point
                    curr_row[j] = prior_row[j] and s1[i - 1] == s3_char
                else:
                    # check if prior char matches up to current char of s1 and s2 curr matches
                    # OR prior char matches up to curr char of s2 and s1 curr matches
                    curr_row[j] = (
                        curr_row[j - 1] and s2[j - 1] == s3_char
                    ) or (
                        prior_row[j] and s1[i - 1] == s3_char
                    )

            prior_row = curr_row

        return curr_row[-1]


    def isInterleave2D(self, s1: str, s2: str, s3: str) -> bool:
        """
        2D DP (after reading solution:
        - Idea is to track if there is a valid combination up to index i1 in s1 and i2 in s2
        - We can initialize the DP array to with len(s1) + 1 rows, and len(s2) + 1 cols
            - +1 to set the 0-len prefix to True
        - Nested for loops, iterating of idxs of len(s1) + 1 and len(s2) + 1 (+1 to fill array)
            - If both idxs are 0, set to True
            - if i == 0, dp row idx is 1 due to longer DP
                - need to check if dp[0][j-1] is True AND if s2[j-1] == s3[0 + j - 1]
            - Need to check if either is true:
                - up to prior char w/last char in s1 matches AND current char of s2 matches
                    - dp[i - 1][j] and s2[j - 1] == s3[i + j - 1]
                - up to prior char w/last char in s2 matches AND current char of s1 matches
                    - dp[i][j - 1] and s1[i - 1] == s3[i + j - 1]
        - return dp[len(s1)][len(s2)]
        """
        if len(s1) + len(s2) != len(s3):
            return False

        dp = [[False] * (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
                    continue

                s3_char = s3[i + j - 1]
                if i == 0:
                    # checking if s2 to this point matches
                    dp[i][j] = dp[i][j - 1] and s2[j - 1] == s3_char
                elif j == 0:
                    # check if s1 up to this point matches
                    dp[i][j] = dp[i - 1][j] and s1[i - 1] == s3_char
                else:
                    # check if prior char matches current s1 and current char matches s2
                    # OR prior char matches current s2 and current char matches s1
                    dp[i][j] = (
                        dp[i - 1][j] and s1[i - 1] == s3_char
                    ) or (
                        dp[i][j - 1] and s2[j - 1] == s3_char
                    )
        return dp[len(s1)][len(s2)]

    def isInterleaveBFS(self, s1: str, s2: str, s3: str) -> bool:
        """
        BFS: O(s1 * s2) CC ; O(2^s3) MC
        - init res = set([(0,0,0,None,0,0)]) rep'ing i1, i2, i3, curr, n1, n2
        - loop while res
            - init nxt_res
            - for el in res
                - if terminated
                    - return True if abs(n1 - n2) < 2
                    - else continue
                - check/handle other terminal conditinos
                - if s1[i1] == s3[i3]:
                    - if curr == s1:
                        - add (i1+1,i2,i3+1,"s1",n1,n2) to nxt_res
                    else:
                        - add (i1+1,i2,i3+1,"s1",n1 + 1,n2) to nxt_res
                - Do the same for s2
            set res = nxt_res
        - return False
        """
        if len(s1) + len(s2) != len(s3):
            return False

        layer = set([(0,0,0,None,0,0)])
        while layer:
            nxt_layer = set()
            
            while layer:
                i1,i2,i3,curr,n1,n2 = layer.pop()
                if i1 == len(s1) and i2 == len(s2) and i3 == len(s3):
                    if abs(n1 - n2) < 2:
                        return True
                    continue
                elif len(s1) == i1:
                    if s2[i2:] == s3[i3:]:
                        if curr == "s2" and abs(n1 - n2) < 2:
                            return True
                        elif curr != "s2" and abs(n1 - (n2 + 1)) < 2:
                            return True
                    continue
                elif len(s2) == i2:
                    if s1[i1:] == s3[i3:]:
                        if curr == "s1" and abs(n1 - n2) < 2:
                            return True
                        elif curr != "s1" and abs(n1 - n2 + 1) < 2:
                            return True
                    continue
                elif len(s3) == i3:
                    continue

                if s1[i1] == s3[i3]:
                    if curr == "s1":
                        nxt_layer.add((i1+1, i2, i3+1, "s1", n1, n2))
                    else:
                        nxt_layer.add((i1+1, i2, i3+1, "s1", n1 + 1, n2))
                
                if s2[i2] == s3[i3]:
                    if curr == "s2":
                        nxt_layer.add((i1, i2+1, i3+1, "s2", n1, n2))
                    else:
                        nxt_layer.add((i1, i2+1, i3+1, "s2", n1, n2 + 1))

            layer = nxt_layer

        return False

    def isInterleaveDFS(self, s1: str, s2: str, s3: str) -> bool:
        """
        - For every char where the current head of s1 and s2 match, could branch
        - Some kind of DFS could be best — only need to get find one correct answer, 
          even if there are multiple
        - Could we store partial matches to avoid re-computing matches?
        
        Brute-force backtrack:
        - Init n1, n2 = 0, representing number of sub strings for s1 and s2
        - Init dict keyed by (s1_idx, s2_idx, s3_idx) with vals of form Set[(n1,n2)]
        - Create helper that takes s1, s2, s3, s1_idx, s2_idx, s3_idx, curr_str, [n1, n2]
            - if s1_idx == len(s1) and same for s2_idx
                - return [n1, n2]
            - if s1[s1_idx] == s3[s3_idx]
                - if curr_str != s1, increment n1
                - increment s1_idx
                - Call helper
                    - append [returned_n1 - n1 + 1, returned_n2 - n2] cache[(s1_idx, s2_idx, s3_idx)]
                - decrement s1_idx
                - if curr_str != s1, decrement n1
            - do same for s2
            - return False
        - Call helper and return it's value

        String cutting: (w/o cutting for CC/MC): O(s1 * s2) CC ; O(s1 * s2) MC
        Helper: s1, s2, s3, curr_str, cache
        - if len(s2) == 0 and s1 == s3:
            - Set cache[(s1, s2, s3)] = [(1, 0)]
            - return [(1, 0)]
        - else if len(s1) == 0 and s2 == s3:
            - Set cache[(s1, s2, s3)] = [(0, 1)]
            - return [(0, 1)]
        - else if (s1,s2,s3) in cache, return that

        - if s1 and s1[0] == s3[0]:
            - hres = call helper with string chops
            - if curr_str == s1:
                results = hres
            - else:
                results = hres * [(1,0)]
        - Same for s2, but append to results, rather than set
        - Add results to cache
        - Return results
        - Call helper to get possible n1, n2 combos
        - Iterate over combos — if abs(n1 - n2) < 2, return True
        - Return False
        """
        cache: dict[tuple[int,int,int], Set[tuple[int,int]]] = {}

        def dfs(i1: int, i2: int, i3: int, curr: str|None):
            el = (i1, i2, i3)
            if el in cache:
                return cache[el]
            elif len(s2) == i2:
                if s1[i1:] == s3[i3:]:
                    cache[el] = set([(1,0)])
                else:
                    cache[el] = set()
                return cache[el]
            elif len(s1) == i1:
                if s2[i2:] == s3[i3:]:
                    cache[el] = set([(0,1)])
                else:
                    cache[el] = set()
                return cache[el]
            elif len(s3) == i3:
                cache[el] = set()
                return cache[el]

            results = set()
            if s1[i1] == s3[i3]:
                s1_res = dfs(i1 + 1, i2, i3 + 1, "s1")
                if curr == "s1":
                    results = s1_res
                else:
                    for s1n1,s1n2 in s1_res:
                        results.add((s1n1 + 1, s1n2))

            if s2[i2] == s3[i3]:
                s2_res = dfs(i1, i2 + 1, i3 + 1, "s2")
                if curr == "s2":
                    results.update(s2_res)
                else:
                    for s2n1,s2n2 in s2_res:
                        results.add((s2n1, s2n2 + 1))

            cache[el] = results
            return results

        results = dfs(0, 0, 0, None)

        for n1,n2 in results:
            if abs(n1 - n2) < 2:
                return True
        return False

17700