8 line Python, search from Frond and End, beat 90% (with some comments)


  • 0
    X

    I have this variable s, 0 means search from Front and 1 means search from End.
    p[0] indicates the steps we move from Front, p[1] indicates the steps from End.
    now[0] stores results of searching from Front, now[1] stores results of searching from End. Each result is a pair(a,b), meaning that "I need to match s1[a] and s2[b] next".
    steps = [1, -1], 1 means match forward (next is index + 1), -1 means backward (next is index - 1)

    class Solution(object):
        def isInterleave(self, s1, s2, s3):
            """
            :type s1: str
            :type s2: str
            :type s3: str
            :rtype: bool
            """
            p, now, step, next = [0, len(s3) - 1], [set([(0, 0)]), set([(len(s1), len(s2))])], [1, -1], set()
            # steps we made is less than the length of s3
            while p[0] + len(s3) - 1 - p[1] < len(s3):
                # choose the direction that contains less results to expand
                s = 0 if len(now[0]) <= len(now[1]) else 1
                for x in now[s]:
                    # use s1
                    if x[0] - s >= 0 and x[0] - s < len(s1) and s3[p[s]] == s1[x[0] - s]: next.add((x[0] + step[s], x[1]))
                    # use s2
                    if x[1] - s >= 0 and x[1] - s < len(s2) and s3[p[s]] == s2[x[1] - s]: next.add((x[0], x[1] + step[s]))
                now[s], p[s], next = next, p[s] + step[s], set()
            # contains same result? they met!
            return len(now[0] & now[1]) > 0
    

Log in to reply
 

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