Thanks to @ChuntaoLu 's solution.
Based on his solution I wrote these codes and comments which I think are more understandable and easy-to-read in the first glimpse.
Hope this can help people who has no idea how to start with DP solution
class Solution(object): def isMatch(self, s, p): p = Solution.removeConsecutive('*', p) return self.isMatchHelper(s, p) # a little bit of optimization @staticmethod def removeConsecutive(mark, p): i = 0 while i < len(p): if i+1 < len(p) and p[i] == mark and p[i+1] == mark: p = p[0:i] + p[i+1:] else: i += 1 return p def isMatchHelper(self, s, p): """ :type s: str :type p: str :rtype: bool """ DP = [True] + [False for _ in range(len(s))] for i in range(1, len(p)+1): next_itr = [DP and p[i-1] == '*'] + [False for _ in range(len(s))] for j in range(1, len(s)+1): if p[i-1] == '?': next_itr[j] = DP[j-1] elif p[i-1] == '*': next_itr[j] = DP[j] or next_itr[j-1] else: next_itr[j] = DP[j-1] and p[i-1] == s[j-1] DP = next_itr return DP[-1] # For a 2d table, dp[i][j] would mean whether sub-pattern p[:i] matches sub-string s[:j]. # Most tricky part is when the current pattern letter is *, suppose its index is i-1, p[:i] will # match sub-string s[:j] if p[:i] matches s[:j-1] or p[:i-1] matches s[:j], 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. # # so the pseudo code of 2d dp solution would be: # initial DP[:] # for i = 1:len(p) # for j = 1:len(s) # if p[i-1] is '?': # DP[i][j] = DP[i-1][j-1] # if p[i-1] is regular character: # DP[i][j] = DP[i-1][j-1] and p[i-1] equals s[j-1] # if p[i-1] is '*': # DP[i][j] = ( DP[i][j-1] // since '*' can represent multiple characters # or DP[i-1][j] // since '*' can represent empty characters # return DP[end][end]