97. Interleaving String

https://leetcode.com/problems/interleaving-string/

Description

Given strings s1, s2, and s3, find whether s3 is formed by an interleaving of s1 and s2.

An interleaving of two strings s and t is a configuration where s and t are divided into n and m substrings respectively, such that:

• s = s1 + s2 + ... + sn
• t = t1 + t2 + ... + tm
• |n - m| <= 1
• The interleaving is s1 + t1 + s2 + t2 + s3 + t3 + ... or t1 + s1 + t2 + s2 + t3 + s3 + ...

Note: a + b is the concatenation of strings a and b.

Answer

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        # Edge case
        l, m, n = len(s1), len(s2), len(s3)
        if l + m != n:
            return False
        
        # Init cache
        cache = {}
        
        # Helper method
        def helper(i, j, k) -> bool:
            if k == n:
                return True
            if (i, j) in cache:
                return cache[(i, j)]
            ans = False
            if i < l and s1[i] == s3[k]:
                ans |= helper(i+1, j, k+1)
            if j < m and s2[j] == s3[k]:
                ans |= helper(i, j+1, k+1)
            cache[(i, j)] = ans
            return ans
        
        return helper(0, 0, 0)

Solution

From the nature of the problem, we can tell that this is a dynamic programming problem — we can work our way up towards the larger global solution by utilizing smaller subparts of the problem.

The core of the logic lies in the helper function, which has three arguments: i, j, and k. These three values are used to represent the current position/index in the strings s1, s2, and s3, respectively.

TODO

One small optimization: we can remove k from the arguments to the helper method, and inside the method, we can replace all instances of k with i + j instead.