Python DP without DP table

  • 1
    class Solution(object):
        def isInterleave(self, s1, s2, s3):
            arr = set([(-1, -1)])
            n1, n2 = len(s1), len(s2)
            if n1 + n2 != len(s3): return False
            for c in s3:
                tmp = set()
                for a1, a2 in arr:
                    if a1+1 < n1 and s1[a1+1] == c:
                        tmp.add((a1+1, a2))
                    if a2+1 < n2 and s2[a2+1] == c:
                        tmp.add((a1, a2+1))
                if len(tmp) == 0:
                    return False
                arr = tmp
            return True

Log in to reply

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