1
\$\begingroup\$

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?
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.