Python - three solutions - 1) recursion with momerize 2) DP 3) finate state machine
I met a simpler version of this problem during Mircrosoft on-site interview. During the on-site, there is only one wildcard \'?\' and \'?\' means zero or one ar
I met a simpler version of this problem during Mircrosoft on-site interview. During the on-site, there is only one wildcard \'?\' and \'?\' means zero or one arbitrary charecter. I solved this simpler wildcard matching problem using recursion. Then I came to Leetcode to find the wildcard matching problem and I found this problem #44.\n\nHere I provide my three solutions\n1. **Recursion with memorization**. Without memorization and some other pruning techniques, there will be Time Limit Exceeded. My memorization is inspired from this [post](https://leetcode.com/problems/wildcard-matching/discuss/17811/My-three-C%2B%2B-solutions-(iterative-(16ms)-and-DP-(180ms)-and-modified-recursion-(88ms))). The key is to notice the following. Let *s_sub* be a substring of *s*, and let *p_sub* be a substring of *p*. If *s_sub* and *p_sub* doesn\'t match, then *s* and *p* doesn\'t match.\n2. **Dynamic programming**. My first attemp failed because I had issue defining the subproblem.  Bad definition: let dp[i][j] be {0, 1, 2, 3, 4, ...}, the longest length of substring that s[1, ..., i ] match p[1, ..., j ]. I stuggled a lot with this subproblem definition. Then I looked at the discussion and fixed the difinition. Good definition: let dp[i][j] be {0, 1}, where {0} means s[1, ..., i ] doesn\'t match p[1, ..., j ], and {1} means s[1, ..., i ] match p[1, ..., j ]. Under this definition, I solve the problem.\n3. **Finite state machine**. This is the most elegant solution. I like this solution the most. I am inspired from this [post](https://leetcode.com/problems/wildcard-matching/discuss/138878/Finite-state-machine-with-Python-and-dictionary.-13-lines-O(p%2Bs)-time). First build a finate state machine using the pattern p, then run the machine with the input string s.\n\n\n```\n\nclass Solution:\n    \'\'\'Recursion solution -- with memorization. \n\t   Time beat 86%.\n    \'\'\'\n    def __init__(self):\n        self.memorize = []  # memorize the smaller substrings s[i:] and p[j:] that doesn\'t match\n\n    def update_memorize(self, s, i, p, j):\n        s_no_match_new = len(s) - i  # the last s_no_match charecters of s\n        p_no_match_new = len(p) - j  # the last p_no_match charecters of p\n        new_memorize = []\n        keep_new = True\n        for s_no_match_old, p_no_match_old in self.memorize:\n            if s_no_match_old < s_no_match_new or p_no_match_old < p_no_match_new:\n                new_memorize.append((s_no_match_old, p_no_match_old))\n            if s_no_match_old < s_no_match_new and p_no_match_old < p_no_match_new:\n                keep_new = False\n        if keep_new:\n            new_memorize.append((s_no_match_new, p_no_match_new))\n        self.memorize = new_memorize\n\n    def check_memorize(self, s, i, p, j):\n        prune = False\n        s_sub_len = len(s) - i\n        p_sub_len = len(p) - j\n        for s_no_match, p_no_match in self.memorize:\n            if s_sub_len >= s_no_match and p_sub_len >= p_no_match:\n                prune = True  # when two smaller substrings of s[i:] and p[j:] don\'t match, s[i:] and p[j:] is guaranteed not to match, so prune it\n                break         # the  two smaller substrings here are the last s_no_match charecters of s and the last p_no_match charecters of p\n        return prune\n\n    def isMatch_helper(self, s: str, p: str) -> bool:\n        if len(s) == 0 and len(p) == 0:  # both match to the end\n            return True\n        if len(s) == 0 or len(p) == 0:   # one comes to the end but the other not\n            return False\n        if s[0] == p[0] or p[0] == \'?\':  # match\n            return self.isMatch_helper(s[1:], p[1:])\n        if s[0] != p[0] and p[0] == \'*\':\n            i, j = 0, 0\n            while j < len(p):            # j points to the first char that is not \'*\'\n                if p[j] != \'*\':\n                    break\n                j += 1\n            counter = 0\n            for k in range(j+1, len(p)): # for pruning the search space for i\n                if p[k] != \'*\':\n                    counter += 1\n            while i < len(s)-counter and j < len(p):\n                if s[i] == p[j] or (s[i] != p[j] and p[j] == \'?\'):\n                    if self.check_memorize(s, i, p, j):\n                        return False\n                    if self.isMatch_helper(s[i:], p[j:]):\n                        return True\n                    else:\n                        self.update_memorize(s, i, p, j)\n                i += 1\n        return False                     # case for s[0] != p[0] and p[0] is not a wildcard:\n\n    def isMatch(self, s: str, p: str) -> bool:\n        s = s + \'1\'\n        p = p + \'1\'  # so that the last charecter is not \'*\'. Of course there are other ways to deal with it.\n        return self.isMatch_helper(s, p)\n\n\nclass Solution2:\n    \'\'\'DP solution, nice solution. First I defined the subproblem so that dp[i][j] are {0, 1, 2, 3...}, this way is somewhat hard, so failed\n       The right way of defining the subproblem is that dp[i][j] is {True,False}.\n\t   Time beat 15%.\n    \'\'\'\n    def isMatch(self, s: str, p: str) -> bool:\n        m, n = len(s), len(p)\n        dp = [[0 for _ in range(n+1)] for _ in range(m+1)]\n        dp[0][0] = 1\n        j = 1\n        while j-1 < len(p):\n            if p[j-1] != \'*\':\n                break\n            dp[0][j] = 1\n            j += 1\n        for i in range(1, m+1):\n            for j in range(1, n+1):\n                if s[i-1] == p[j-1] or p[j-1] == \'?\':\n                    if dp[i-1][j-1]:              #  precise match\n                        dp[i][j] = 1\n                if s[i-1] != p[j-1] and p[j-1] == \'*\':\n                    if dp[i][j-1] or dp[i-1][j]:  # \'*\' either {skip} or {matching more charecters}\n                        dp[i][j] = 1\n        return dp[m][n]\n\n\nclass Solution3:\n    \'\'\'Finite state machine (FSM) solution. elegant\n       reference: https://leetcode.com/problems/wildcard-matching/discuss/138878/Finite-state-machine-with-Python-and-dictionary.-13-lines-O(p%2Bs)-time\n\t   Time beat 77%.\n    \'\'\'\n    def isMatch(self, s: str, p: str) -> bool:\n        # step 1: build a FSM: 1) state 2) transition\n        state = 0\n        transition = {}\n        for char in p:\n            if char != \'*\':\n                transition[(state, char)] = state + 1\n                state += 1\n            else:\n                transition[(state, char)] = state\n        final_state = state\n        # step 2: start running the FSM\n        states = set([0])\n        for char in s:\n            new_states = set()\n            for state in states:\n                for token in [char, \'*\', \'?\']:\n                    next_state = transition.get((state, token))\n                    if next_state is not None:\n                        new_states.add(next_state)\n            states = new_states\n        return final_state in states\n\n```
[]