Python DFS solution from grapeot's 8ms BFS solution

  • 0
    class Solution:
    # @return a boolean
    def isInterleave(self, s1, s2, s3):
        n, m = len(s1), len(s2)
        if n+m != len(s3):
            return False
        stack, visited = [(0, 0)], set()
        while stack:
            y, x = stack.pop()
            if y+x == len(s3):
                return True
            if x+1 <= n and s1[x] == s3[y+x] and (y, x+1) not in visited:
                visited.add((y, x+1))
                stack.append((y, x+1))
            if y+1 <= m and s2[y] == s3[y+x] and (y+1, x) not in visited:
                visited.add((y+1, x))
                stack.append((y+1, x))
        return False

Log in to reply

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