Day 2: Interleaving String

Problem Link:

https://leetcode.com/explore/challenge/card/june-leetcoding-challenge-2021/603/week-1-june-1st-june-7th/3765/

Problem Statement:

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 they are divided into non-empty substrings 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.

Example 1:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true
Explanation:

Example 2:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output: false

Example 2:

Input: s1 = "", s2 = "", s3 = ""
Output: true

Constraints:

• 0 <= s1.length, s2.length <= 100
• 0 <= s3.length <= 200
• s1, s2, and s3 consist of lowercase English letters.

My Solution:

from functools import lru_cache
def isInterleave(self, s1: str, s2: str, s3: str) -> bool:        
    if len(s3) != len(s1) + len(s2): return False
        
    @lru_cache(None)
    def helper(s1, s2, s3):
        if not s1: return s2 == s3 #If s1 is empty
        if not s2: return s1 == s3 #If s2 is empty
        #Check for both the cases, i.e. char match with s1[0] or it matches with s2[0].
        return (
            s1[0] == s3[0] and helper(s1[1:], s2, s3[1:])) 
            or (s2[0] == s3[0] and helper(s1, s2[1:], s3[1:]))                    
    return helper(s1, s2, s3)

Explanation:

This problem will seem easy if you are able to conclude that it can be solved by solving its sub-problems.

If s1[0] and s2[0] both match s3[0], we have 2 cases, i.e. either take that character from s1 and repeat the procedure for s1[1::] and s2 else take that character from s2 and repeat the procedure for s1 and s2[1::]. Thus, we take isInterleave(s1[1:], s2, s3[1:]) || isInterleave(s1, s2[1:], s3[1:]). If only one of them match, we only recur once.

The problem then gets reduced down to a subproblem. We continue to do this until s1, s2, and s3 are all empty. Hence, we get the solution to the problem.

That’s it!

If you are interested in solving more problems, do follow me and join me on this journey.

See you tomorrow!

Cheers!