6/21/2020

[LeetCode] 97. Interleaving String

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

Use DFS to reconstruct the interleaving string. Use memorization to avoid duplicate validation.

Time Complexity = O ( M * N )    M = len(s1),  N = len(s2)

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        
        @lru_cache(maxsize = None)
        def dfs(i, j, k):
            if k >= len(s3):
                return i == len(s1) and j == len(s2)
            
            if i < len(s1) and s3[k] == s1[i]:
                if dfs(i + 1, j, k + 1):
                    return True
            
            if j < len(s2) and s3[k] == s2[j]:
                if dfs(i, j + 1, k + 1):
                    return True
            
            return False
        
        
        return dfs(0, 0, 0)

No comments:

Post a Comment