Beat 99% runtime 103 O(n) time O(1) space.
first approach works and run beats over 90%, second approach cannot work but wanna seek advice.\n\nLoop\n\n1. keep two pointers in S and P here i and j\n\n2. if
first approach works and run beats over 90%, second approach cannot work but wanna seek advice.\n\nLoop\n\n1. keep two pointers in S and P here i and j\n\n2. if S[i] == P[j] or P[j] == '?' we keep moving\n3. if '*' exist in P then we mark the position in P as star and mark position in s as s_star\n4. Loop over s until S[i] == P[star + 1]\notherwise\n  False\n\nnote that S = 'a' P = 'a*******' is still True\nSo we need to loop over P to check this case  \n\n\n \nif we can compare p to the end that  means True\n\n    class Solution(object):\n    def isMatch(self, s, p):\n        """\n        :type s: str\n        :type p: str\n        :rtype: bool\n        """\n        i = 0\n        j = 0\n        star = -1\n        s_star = 0\n        s_len = len(s)\n        p_len = len(p)\n        while i < s_len:\n            if i < s_len and j < p_len and (s[i] == p[j] or p[j] == '?'):\n                i += 1\n                j += 1\n            elif j < p_len and p[j] == '*':\n                star = j\n                s_star = i\n                j += 1\n            elif star != -1:\n                j = star + 1\n                s_star += 1\n                i = s_star\n            else:\n                return False\n        while j < p_len and p[j] == '*':\n            j += 1\n        return j == p_len\n        \nI have also Tried more traditional method with O(MN) space and Time but get LTE suggestions?\n\n\n    class Solution(object):\n    def isMatch(self, s, p):\n        """\n        :type s: str\n        :type p: str\n        :rtype: bool\n        """\n        s_len = len(s)\n        p_len = len(p)\n        dp = [[False for _ in range(p_len + 1)] for _ in range(s_len + 1)]\n        dp[0][0] = True\n        for col in range(1, p_len + 1):\n            dp[0][col] = dp[0][col - 1] and p[col - 1] == '*'\n        \n        for row in range(1, s_len + 1):\n            for col in range(1, p_len + 1):\n                if p[col - 1] == '*':\n                    dp[row][col] = dp[row][col - 1] or dp[row - 1][col - 1]\n                else:\n                    dp[row][col] = dp[row - 1][col - 1] and (s[row - 1] == p[col - 1] or p[col - 1] == '?')\n        return dp[-1][-1]
['Dynamic Programming']