Greatly Explained Two Methods DFS + Memo & DP in Python, Very Easy to Understand!!!
Very classical question that could be solved using DFS + Memo & DP!\n\nGeneral View:\nThe challenge part is * .\nIt could match any number of characters.\nSo ho
**Very classical question** that could be solved using **DFS + Memo** & **DP**!\n\n**General View:**\nThe challenge part is * .\nIt could match any number of characters.\nSo how to deal with * is **the key**!\n\n**Take an example:**\nIf we match * with every possible number of characters, then the divisions in each level could be many\n```\n\t\t  (*ab, abc)\n\t  /     |       \\     \\\n(ab, abc) (ab, bc) (ab, c) (ab, \'\')\n```\nIf we give match only two options, not match or match (* will stay for next level), the the divisions in each level is two.\n```\n\t(*ab, abc)\n\t  /   \\\n(ab, ab)  (*ab, b)\t  \n```\nIt is obvious that **the latter one is better**! That is how we will deal with * .\n\n**Method 1:**\n**DFS + Memoization**\n\nWhenever will come across a * , we will generate two paths, either **not match any** or **match**.\nHowever, that is not enough, since we might have duplicate states when we have ***continuing*** * .\n**For example:**\n```\n       (**, abc)\n\t    /   \\\n\t(*, abc)  (**, bc)\n\t/      \\     /   \\\n(\'\', abc) (*, bc) (**, c)\n```\nThe state (* , bc) will be reached from different paths. Meaning that we could use **memoization**!\nThe time will be reduced from O(2 ^ n) to O(m * n).\n\nWe will use index of the string as the signature of each state. Every state reached will be stored in the memo hash.\n\n**Time:** O(m * n), m is the length of string s, n is the length of string p\n**Space:** O(m * n)\n\n```\nclass Solution:\n    def isMatch(self, s: str, p: str) -> bool:\n        memo = {}\n        s_index, p_index = 0, 0\n        return self.memo_dfs(s, s_index, p, p_index, memo)\n    \n    def memo_dfs(self, s, i, p, j, memo): \n        \n        if len(p) == j:\n            return len(s) == i\n        \n        if len(s) == i:\n            for index in range(j, len(p)):\n                if p[index] != \'*\':\n                    return False\n            return True\n        \n        if (i, j) in memo:\n            return memo[(i, j)]\n\n        if p[j] != \'*\':\n            matched =  (s[i] == p[j] or p[j] == \'?\') and self.memo_dfs(s, i + 1, p, j + 1, memo)\n        else:  # matched & not matched\n            matched = self.memo_dfs(s, i + 1, p, j, memo) or self.memo_dfs(s, i, p, j + 1, memo)\n        \n        memo[(i, j)] = matched\n        \n        return matched\n```\n\n**Method 2:**\n**DP**\n\nThe idea is very similar, **dp[i][j]** means that by index i of s and by index j of p, whether there is a matching.\n\n**Time:** O(m * n), m is the length of string s, n is the length of string p\n**Space:** O(m * n)\n\n```\nclass Solution:\n    def isMatch(self, s: str, p: str) -> bool:\n        if s is None or p is None:\n            return False\n        \n        m, n = len(s), len(p)\n        \n        dp = [[False] * (n + 1) for _ in range(2)]\n        \n        dp[0][0] = True\n        for i in range(1, n + 1): # the case that p starts with some *\n            dp[0][i] = dp[0][i - 1] and p[i - 1] == \'*\'\n        \n        for i in range(1, m + 1):\n            dp[i % 2][0] = False # Note that: we might miss this!\n            for j in range(1, n + 1):\n                if p[j - 1] == \'*\': # match & no match \n                    dp[i % 2][j] = dp[(i - 1) % 2][j] or dp[i % 2][j - 1]\n                else:\n                    dp[i % 2][j] = dp[(i - 1) % 2][j - 1] and (\n                        s[i - 1] == p[j - 1] or p[j - 1] == \'?\')\n        \n        return dp[m % 2][n]\n```
['Dynamic Programming', 'Depth-First Search', 'Memoization', 'Python']