Using BFS, beat 98%


  • 0
    X

    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:
                        next.add((x[0], x[1] + step[d]))
                        for i in range(x[0], -1 if d else len(s), step[d]):
                            if l[x[1]][0] == "." or s[i] == l[x[1]][0]: next.add((i + step[d], x[1] + step[d]))
                            else: break
                now[d], next = next, set()
            return True
    '''

Log in to reply
 

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