[Python3] - Top-down + Bottom-up DP Solutions
Time Complexity: O(mn)\nSpace Complexity: O(mn)\n\nSome tips I use to become better at Top-down DP (feel free to give suggestions):\n1. When thinking in top-dow
**Time Complexity:** O(m*n)\n**Space Complexity:** O(m*n)\n\n**Some tips I use to become better at Top-down DP (feel free to give suggestions):**\n1. When thinking in top-down DP manner, always begin with termination conditions. (What happens when i reaches the end or when j reaches the end?)\n2. What happens when we encounter a special condition? (e.g. What happens when p[j-1] == \'*\'?)\n3. In a top-down manner, since the **final** result will only be available when we hit the termination condition, when we increment i or j, it means that we can \'omit\' either one or both of them. For instance, when p[j] and s[i] matches or when p[j] equals to the "match everything" special character, we can increment both i and j (by \'omitting\' them and only consider characters after i and after j)\n4. Always think recursively. Memoization can be as simple as one line (which can be achieved by the cache decorator in Python)\n5. Practice and practice. Good luck!\n\n**Steps I follow when I do bottom-up DP (suggestions are welcome):**\n1. Start with base condition (e.g. What if both strings are empty? i.e. dp[0][0] = True. What if one string is empty and another is not? Pre-populate those values)\n2. When we say dp[i][j] = dp[i-1][j-1], it means we can \'increment\' i and j, similar to top-down manner. This is because we can omit calculation for current string and simply "bridge the cap" with the previous results. (Not sure if this makes sense)\n\nHope this helps. When I first started, I remember I was really bad at DP. But as I practice more I\'m getting better every day. Never give up -- I\'m sure you will get there soon.\n\n**Solution 1: Top-down DP (memoization)**\n```python\nclass Solution:\n    def isMatch(self, s: str, p: str) -> bool:\n\t\t@cache\n\t\tdef dp(i, j):\n\t\t\tif j >= len(p):\n\t\t\t\treturn i == len(s)\n\t\t\t# When s reaches the end, p must be empty or contains only * (since * can also be used to represent empty string)\n\t\t\tif i >= len(s):\n\t\t\t\treturn not p[j:] or p[j:] == \'*\'*len(p[j:])\n\t\t\t# Since \'*\' can be used to represent any sequence of characters including empty string, we can either increment i or j.\n\t\t\tif p[j] == \'*\':\n\t\t\t\treturn dp(i+1, j) or dp(i, j+1)\n\t\t\tif p[j] in {s[i], \'?\'}:\n\t\t\t\treturn dp(i+1, j+1)\n\t\t\treturn False\n\t\treturn dp(0, 0)\n```\n\n**Solution 2: Bottom up DP**\n```python\nclass Solution:\n    def isMatch(self, s: str, p: str) -> bool:\n        m, n = len(s), len(p)\n        dp = [[False]*(n+1) for _ in range(m+1)]\n        # When s and p are both empty, they must match.\n        dp[0][0] = True\n        \n        for j in range(1, n+1):\n            if p[j-1] != \'*\':\n                break\n            dp[0][j] = True\n        \n        for i in range(1, m+1):\n            for j in range(1, n+1):\n                if p[j-1] in {s[i-1], \'?\'}:\n                    dp[i][j] = dp[i-1][j-1]\n                elif p[j-1] == \'*\':\n                    dp[i][j] = dp[i-1][j] or dp[i][j-1]\n        return dp[-1][-1]\n```\n\nEdit: \n**Solution 1 (no slicing)**\n```python\nclass Solution:\n    def isMatch(self, s: str, p: str) -> bool:\n        @cache\n        def dp(i, j):\n            if j >= len(p):\n                return i == len(s)\n            if i < len(s) and p[j] in {s[i], \'?\'}:\n                return dp(i+1, j+1)\n            if p[j] == \'*\':\n                if i < len(s):\n                    return dp(i+1, j) or dp(i, j+1)\n                return dp(i, j+1)\n        return dp(0, 0)\n```
['Dynamic Programming', 'Python']