InterleavingStrings.py

# Question link - https://leetcode.com/problems/interleaving-string/description/?envType=study-plan-v2&envId=top-interview-150

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        # Sol2: Dynamic Solutions
        # In this can optimised to O(m.n)
        if len(s1) + len(s2) != len(s3):
            return False 

        dp = [[False] * (len(s2)+1) for i in range(len(s1)+ 1)]
        # Initalize the base position dp 
        dp[len(s1)][len(s2)] = True 

        # Traverse the strings in revesre order 
        for i in range(len(s1),-1,-1):
            for j in range(len(s2),-1,-1):
                # Conditions for the out of bounce 
                if i < len(s1) and s1[i] == s3[i+j] and dp[i+1][j]:
                    dp[i][j] = True 
                if j < len(s2) and s2[j] == s3[i+j] and dp[i][j+1]:
                    dp[i][j] = True
        return dp[0][0]


        # # Sol1 : Recursive (Brute - force approch)
        # # This can be reduce to O(m.n) in caching 
        # dp = {}
        # # k = i + j
        # # The function for the DFS
        # def dfs(i , j):
        #     if i == len(s1) and j == len(s2):
        #         return True
        #     #Cache conditions 
        #     if (i,j) in dp:
        #         return dp[(i,j)]

        #     # Out of bounce condition 
        #     if i < len(s1) and s1[i] == s3[i+j] and dfs(i+1,j):
        #         return True 
        #     if j < len(s2) and s2[j] == s3[i+j] and dfs(i,j+1):
        #         return True

        #     dp[(i,j)] = False 
        #     return False 

        # return dfs(0,0)