【Leetcode】44. Wildcard Matching

class Solution(object):
    def isMatch(self, s, p):
        """
       '?' Matches any single character.
       '*' Matches any sequence of characters (including the empty sequence).
        use dp[i][j] means pattern pattern[:j] could match string string[:i]
        The first step we should do is to init dp[0][*] and dp[*][0], the border:
        dp[*][0]:
        if p[0] == "*": dp[*][0] = True , because * could match any sequencet
        if p[0] == s[0] or p[0] == "?" : dp[0][0] = True
        others are all False
        dp[0][*]:  notice case "b","**?" and "b","?*?"
        dp[0][0] already calc above
        dp[0][n] depend on p[n] and p[n-1], detail is in following code

        for dp equation
        if s[i] == p[i] or p[i] == "?" or dp[i][j] = dp[i-1][j-1]
        if p[j] == "*", dp[i][j] == dp[i][j-1] or dp[i-1][j](if p[:j] match s[:i-1] ,and is also could macth s[:i])
        """
        if len(s) == 0 or len(p) == 0:
            if len(s) == 0 and len(p) != 0:
                if len(p) == 1 and p[0] == "*":
                    return True
                else:
                    return False
            else:
                return len(s) == 0
        dp = [[False] * len(p) for _ in range(len(s))]

        if p[0] == "*":
            for i in range(len(dp)):
                dp[i][0] = True
        else:
            if p[0] == "?" or p[0] == s[0]:
                dp[0][0] = True
        flag  = False
        # use a flag to denote whether already match a character (not by * )
        if p[0] == "?" or p[0] == s[0]:
            flag = True
        for j in range(1,len(p)):
            # "b","**?" and "b","?*?"
            if p[j] == "*":
                dp[0][j] = dp[0][j-1]
            else:
                if p[j-1] == "*" and (p[j] == s[0] or p[j] == "?") :
                    if flag:
                        break
                    else:
                         dp[0][j] = dp[0][j-1]
                         flag = True
        for i in range(1, len(dp)):
            for j in range(1, len(dp[0])):
                if s[i] == p[j] or p[j] == "?":
                    dp[i][j] = dp[i-1][j-1]
                if p[j] == "*":
                    dp[i][j] = dp[i-1][j] or dp[i][j-1]
        return dp[-1][-1]