After failed a lot of times trying to cover all found corner cases, I tried this state machine like solution at the first time. Hope this share can help.
There are many corner cases, even using the state machine.
My solution follows an interesting paper using NFA to solve regular expression problem. It is post here. https://swtch.com/~rsc/regexp/regexp1.html It's well written, easy to understand.
My code is not optimized enough. Will do that later :). But hope this can explain the idea at least.
- Each character in the pattern p can be taken as an input for a state. A state changes to others after receiving the input.
- Build a series of state and connect them into a state machine. Give the string s to the machine, and see the result.
class State: def __init__(self, value): self.val = value self.next =  class Solution: def isMatch(self, s, p): # Solution: build a state machine first, and match the string # recursively. def build(p): if not p: return None stack =  for i, e in enumerate(p): # add e if e != '*': state = State(e) if stack: stack[-1].next.append(state) stack.append(state) else: # add * state = State(None) if len(stack) > 1: stack[-1].next.append(state) state.next.append(stack[-1]) stack[-2].next.remove(stack[-1]) stack[-2].next.append(state) stack[-1] = state elif len(stack) == 1: stack.next.append(state) state.next.append(stack) stack = state else: state.next.append(state) stack.append(state) stack[-1].next.append(None) # final state return stack def match(s, p): # if dead loop, return False if (s, p) in states: return False states.add((s, p)) # if read end return judgement if not p: if not s: return True return False if p.val == None: return any([match(s, np) for np in p.next]) subs = s[:len(p.val)] if comp(subs, p.val): return any([match(s[len(p.val):], np) for np in p.next]) return False def comp(s, p): # support only char and . # print s, p if len(s) != len(p): return False for i, c in enumerate(s): if c != p[i] and p[i] != '.': return False return True head = build(p) if s and not head: return False states = set() ans = match(s, head) return ans