Python DP solution
For a 2d table, dp[i][j] would mean whether sub-pattern p[:i + 1] matches sub-string s[:j + 1].\nMost tricky part is when the current pattern letter is *, suppo
For a 2d table, dp[i][j] would mean whether sub-pattern p[:i + 1] matches sub-string s[:j + 1].\nMost tricky part is when the current pattern letter is `*`, suppose its index is `i`, p[:i + 1] will match sub-string s[:j + 1] if p[:i + 1] matches s[:j] *or* p[:i] matches s[:j + 1], namely current cell value is true if its top or its left is true.  Since the current row only depends on the previous row, we can use two rolling lists to do the dp instead of a matrix.\n    \n    def isMatch(self, s, p):\n        l = len(s)\n        if len(p) - p.count('*') > l:\n            return False\n        dp = [True]  + [False] * l\n        for letter in p:\n            new_dp = [dp[0] and letter == '*']\n            if letter == '*':\n                for j in range(l):\n                    new_dp.append(new_dp[-1] or dp[j + 1])\n            elif letter == '?':\n                new_dp += dp[:l]\n            else:\n                new_dp += [dp[j] and s[j] == letter for j in range(l)]\n            dp = new_dp\n        return dp[-1]
['Python']