# Wildcard Matching with DFS and FSM

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 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"

1. Are the time complexity of DFS and BFS the same?
2. Is there something wrong with my code?