LC 0097 [M] Interleaving String - ALawliet/algorithms GitHub Wiki

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:        
        if (len(s1) + len(s2)) != len(s3):
            return False
        
        dp = {}

        @cache
        def dfs(i, j):
            # if (i, j) in dp:
                # return dp[(i, j)]
            
            if i == len(s1) and j == len(s2):
                return True
            
            choose_s1 = i < len(s1) and s1[i] == s3[i+j] and dfs(i+1, j)
            choose_s2 = j < len(s2) and s2[j] == s3[i+j] and dfs(i, j+1)
            
#             if (choose_s1 or choose_s2):
#                 dp[(i,j)] = True
#             else:
#                 dp[(i,j)] = False
                
#             return dp[(i,j)]
            return (choose_s1 or choose_s2)
        
        return dfs(0,0)

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        if (len(s1) + len(s2)) != len(s3):
            return False

        ROWS = len(s2)
        COLS = len(s1)

        T = [ [0 for c in range(COLS + 1)] for r in range(ROWS + 1) ]
        
        T[0][0] = 1

        for r in range(1, ROWS + 1):
          if s2[r-1] == s3[r-1] and T[r-1][0] == 1:
            T[r][0] = 1

        for c in range(1, COLS + 1):
          if s1[c-1] == s3[c-1] and T[0][c-1] == 1:
            T[0][c] = 1

        for r in range(1, ROWS + 1):
          for c in range(1, COLS + 1):
            rc = r + c # diag
            if (s2[r-1] == s3[rc-1] and T[r-1][c] == 1) or (s1[c-1] == s3[rc-1] and T[r][c-1] == 1):
              T[r][c] = 1

        return T[-1][-1]