I'm trying to solve Wildcard Matching on LeetCode. I found a great solution using the Finite-state machine. The author builds an FSM and searches with BFS.
I rewrite the solution with the same idea (FSM) but use depth-first search (DFS):
class Solution:
def isMatch(self, s: str, p: str) -> bool:
# build the fsm
fsm = {}
state = 0
for i in range(len(p)):
if p[i] == "*":
# connect to state itself
fsm[state, p[i]] = state
else:
fsm[state, p[i]] = state + 1
state += 1
self.accept = state
self.fsm = fsm
return self.dfs(s, idx=0, state=0)
def dfs(self, s: str, idx: int, state: int) -> bool:
"""deep first search through the finite state machine"""
if idx == len(s):
# processing string finished
if state == self.accept:
return True
else:
return False
for value in [s[idx], "*", "?"]:
if (state, value) not in self.fsm:
# invaild state
continue
next_state = self.fsm[state, value]
if self.dfs(s, idx + 1, next_state):
return True
return False
Since we need to iterate the whole string s, I think the time complexity of DFS and BFS are the same. However, I had the Time Limit Exceeded on the testing case:
"babbbbaabababaabbababaababaabbaabababbaaababbababaaaaaabbabaaaabababbabbababbbaaaababbbabbbbbbbbbbaabbb"
"b**bb**a**bba*b**a*bbb**aba***babbb*aa****aabb*bbb***a"
- Are the time complexity of DFS and BFS the same?
- Is there something wrong with my code?
