🏠

Interleaving String


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

Very simple DFS with memoization. Shouldn’t be a hard exercise!

Algorithm

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        def dfs(i1, i2, i3, memo) -> bool:
            # If reached end of s3, true if other two strings are also empty
            if i3 == len(s3):
                return i1 == len(s1) and i2 == len(s2)
            
            # If reached end of s1, true if rest of s2 and s3 are equal
            if i1 == len(s1):
                return s2[i2:] == s3[i3:]

            # If reached end of s2, true if rest of s1 and s3 are equal
            if i2 == len(s2):
                return s1[i1:] == s3[i3:]
            
            # If next char in s3 isn't equal to either in s1 or s2, FALSE!
            if s1[i1] != s3[i3] and s2[i2] != s3[i3]:
                return False
            
            # Next letter is only from s1
            if s1[i1] == s3[i3] and s2[i2] != s3[i3]:
                return dfs(i1+1, i2, i3+1, memo)

            # Next letter is only from s2
            if s1[i1] != s3[i3] and s2[i2] == s3[i3]:
                return dfs(i1, i2+1, i3+1, memo)

            # If we've already seen this state, return it
            if memo.get((i1, i2)) is not None:
                return memo[(i1, i2)]

            # If next char in s3 is equal to both in s1 and s2, recurse on both and store answer
            memo[(i1, i2)] = (
                dfs(i1+1, i2, i3+1, memo) or
                dfs(i1, i2+1, i3+1, memo)
            )
            return memo[(i1, i2)]

        return dfs(0, 0, 0, {})

 

Issues & PRs welcome ♥️
Powered by Hugo - Theme beautifulhugo