# Using BFS, beat 98%

• It's a bit long though. But the idea is simple, BFS from Front and End.

I firstly convert `p` to a list of character and character + "*", named `l`. Then `s` and `l` need to be matched. I search from Front and End of `l`.

I use `now` to log all the results now (where are we). `now[0]` is the results that search from Front, `now[1]` is from End. Function `good` checks if `now[0]` and `now[1]` met (thus, we found the answer).

``````class Solution(object):
def good(self, a, b, l1, l2):
if (l1, l2) in a or (-1, -1) in b: return True
t = set()
for x in a: t.add((x[0] - 1, x[1] - 1))
return len(t & b) > 0
def isMatch(self, s, p):
l = []
for i in range(len(p)):
if p[i] != "*": l.append(p[i])
else: l[-1] += "*"
now, next, step = [set([(0, 0)]), set([(len(s) - 1, len(l) - 1)])], set(), [1, -1]
while not self.good(now[0], now[1], len(s), len(l)):
d = 0 if len(now[0]) <= len(now[1]) else 1
if len(now[d]) == 0: return False
for x in now[d]:
if not (x[1] >= 0 and x[1] < len(l)): continue
if len(l[x[1]]) == 1:
if l[x[1]] == "." or (x[0] >= 0 and x[0] < len(s) and l[x[1]] == s[x[0]]): next.add((x[0] + step[d], x[1] + step[d]))
else: