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
                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
                return False

        for value in [s[idx], "*", "?"]:
            if (state, value) not in self.fsm:
                # invaild state

            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:

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

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.