Problem Statement in English

You’re given strings s1, s2, and s3. You need to determine if s3 is formed by an interleaving of s1 and s2.

Approach

You simply have to try all possible combinations of s1 and s2 to see if they can form s3. But you can do it efficiently using recursion with memoization to avoid recalculating the same states.

Our overlapping subproblems are defined by the indices of s1 and s2 that we have used so far. We can use a recursive function that takes the current indices of s1 and s2 and checks if the remaining characters can form the remaining part of s3.

The way we move the indices is as follows:

  • If the current character of s1 matches the current character of s3, we can move the index of s1 forward and check the next characters.
  • If the current character of s2 matches the current character of s3, we can move the index of s2 forward and check the next characters.
  • If both characters match, we explore both possibilities.

Also remeber to handle teh edge case that one of the strings is done being processed while the other still has characters left. In that case, we can only continue with the string that still has characters left — essentially, we check if the remaining characters of that string match the remaining characters of s3.

And we’re done!

Solution in Python


class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        M, N = len(s1), len(s2)

        if M + N != len(s3): return False

        @cache
        def dp(i, j):
            if i == M and j == N: return True
            if i == M or j == N:
                if i == M and s2[j:] == s3[i + j:]: return True
                if j == N and s1[i:] == s3[i + j:]: return True
                return False

            k = i + j

            if s1[i] == s3[k] and s2[j] == s3[k]:
                return dp(i + 1, j) or dp(i, j + 1)
            elif s1[i] == s3[k]:
                return dp(i + 1, j)
            elif s2[j] == s3[k]:
                return dp(i, j + 1)
            else:
                return False

        return dp(0, 0)

Complexity

  • Time: $O(M \times N)$
    Since we are using memoization, each state (i, j) will be computed only once, leading to a total of $M \times N$ states.

  • Space: $O(M \times N)$
    Since we are using memoization, each state (i, j) will be computed only once, leading to a total of $M \times N$ states.

And we are done.