Fastest (40ms ~ 44ms) python solution so far using DFS


  • 1
    T
    def isInterleave(self, s1, s2, s3):
        """
        :type s1: str
        :type s2: str
        :type s3: str
        :rtype: bool
        """
        if len(s1) + len(s2) != len(s3):
            return False
        
        self.visited = set()
        return self.search(s1, s2, s3, 0, 0)
        
    def search(self, s1, s2, s3, i1, i2):
        self.visited.add((i1, i2))
        if i1 + i2 == len(s3):
            return True
        else:
            if i1 < len(s1) and s1[i1] == s3[i1 + i2] and (i1+1, i2) not in self.visited and self.search(s1, s2, s3, i1+1, i2):
                return True
            
            if i2 < len(s2) and s2[i2] == s3[i1 + i2] and (i1, i2+1) not in self.visited and self.search(s1, s2, s3, i1, i2+1):
                return True
        
        return False
    

    i1 and i2 are representing the position of each string we want to check against the s3 string.


  • 0
    C
    class Solution(object):
    def isInterleave(self, s1, s2, s3):
        """
        :type s1: str
        :type s2: str
        :type s3: str
        :rtype: bool
        """
        if len(s1)+len(s2) != len(s3): return False
        if len(s1) < len(s2): return self.isInterleave(s2, s1, s3)
        dp = [True] * (len(s2) + 1)
        for i in range(1, len(s2) + 1):
            dp[i] = dp[i-1] and s2[i-1] == s3[i-1]
        
        for i in range(1, len(s1) + 1):
            dp[0] = dp[0] and s1[i-1] == s3[i-1]
            for j in range(1, len(s2) + 1):
                dp[j] =  ( dp[j] and s1[i-1] == s3[i + j -1] ) or ( dp[j - 1] and s2[j-1] == s3[i + j -1] )
                
        return dp[len(s2)]
    

  • 0
    C

    Time Complexity: O(n^2); Space Complexity: O(n).
    It also beats 99% submission in terms of Run Time. (44ms)


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.