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

• 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
``````

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