Different Python solutions with thinking process
Please see and vote for my standard DP solutions for\n10. Regular Expression Matching\n44. Wildcard Matching\n\nMethod 1: standard DP solution using a 2D table 
Please see and vote for my standard DP solutions for\n[10. Regular Expression Matching](https://leetcode.com/problems/regular-expression-matching/discuss/314237/Python-DP-solution-with-detailed-explanation)\n[44. Wildcard Matching](https://leetcode.com/problems/wildcard-matching/discuss/321724/Different-Python-solutions-with-thinking-process)\n\nMethod 1: standard DP solution using a 2D table (1040 ms, beat 17%)\n```\nLet m = len(s), n = len(p), dp[i][j] = whether p[:j] matches s[:i] or not,\nBase cases: \ndp[0][0] = True\ndp[i][0] = False, when i = 1, 2, ..., m\ndp[0][j] = False if p[j-1] is \'?\' or a lowercase letter,  dp[0][j-1] if dp[j-1] == \'*\', when j = 1, 2, ..., n\nRecursive relationship:  for i in range(1, m + 1), for j in range(1, n + 1)\n(1) if p[j-1] is a lowercase letter, dp[i][j] = (p[j-1] == s[i-1]) and dp[i-1][j-1]\n(2) if p[j-1] == \'?\', dp[i][j] = dp[i-1][j-1]\n(3) if p[j-1] == \'*\', dp[i][j] =\n        (i) \'*\' match nothing,  dp[i][j-1]\n   or (ii) \'*\' match at least one character dp[i-1][j]\n```\n```\n    def isMatch(self, s, p):\n        m, n = len(s), len(p)\n        dp = [[False for _ in range(n + 1)] for _ in range(m + 1)]\n        dp[0][0] = True\n        for j in range(1, n + 1):\n            if p[j-1].isalpha() or p[j-1] == \'?\':\n                dp[0][j] = False\n            else:\n                dp[0][j] = dp[0][j-1]\n        for i in range(1, m + 1):\n            for j in range(1, n + 1):\n                if p[j-1].isalpha():\n                    dp[i][j] = (p[j-1] == s[i-1]) and dp[i-1][j-1]\n                elif p[j-1] == \'?\':\n                    dp[i][j] = dp[i-1][j-1]\n                else:\n                    dp[i][j] = dp[i-1][j] or dp[i][j-1]\n        return dp[m][n]\n```\n\nMethod 2: greedy solution with idea of DFS (56ms, beat 96.73%) [reference, tonygogogo\'s comment](https://leetcode.com/problems/wildcard-matching/discuss/17810/Linear-runtime-and-constant-space-solution)\n```\nprev_star stores the position of the previous \'*\' in p\nneed_to_match stores the position of the char in s after a \'*\' matched zero or more chars\nExample:  s = "acdscd", p = "*cd",\nAfter finding the first \'*\', prev_star = 0, need_to_match = 0, \'*\' matches nothing.\ns[0] != p[1], the previous match \'\' of \'*\' (the first branch of DFS) is actually wrong,\nthen reset j = prev_star + 1, increment need_to_match, set i = need_to_match, i.e. \'*\' matches \'a\'.\nWhen we come to i = 3 and j = 3, we know that the previous match \'a\' of \'*\' is wrong,\nthen reset j = prev_match + 1, increment need_to_match, set i = need_to_match, i.e. \'*\' matches \'ac\',\n...\nWhen we have prev_star = 0 and need_to_match = 4 (i.e. \'*\' matches \'acds\'), then get the right match. \n```\n```\n    def isMatch(self, s, p):\n        m, n = len(s), len(p)\n        i, j = 0, 0\n        prev_star, need_to_match = -1, -1\n        while i < m:\n            if j < n and (p[j] == s[i] or p[j] == \'?\'):\n                i, j = i + 1, j + 1\n            elif j < n and p[j] == \'*\':\n                prev_star = j\n                need_to_match = i   # initially let * match nothing\n                j += 1\n            elif prev_star != -1:\n                j = prev_star + 1\n\t\t\t\tneed_to_match += 1  # let * match one more character\n                i = need_to_match\n            else:\n                return False\n        while j < n and p[j] == \'*\':\n            j += 1\n        return j == n\n```
[]