Description

Implement wildcard pattern matching with support for '?' and '*'.

• '?' Matches any single character.
• '*' Matches any sequence of characters (including the empty sequence).
  The matching should cover the entire input string (not partial).

Solution

使用memo记录{<pattern, source>:True/ False}表示是否能match
对于*符号，有三种情况可以考虑，两个都加，分别只加1个

Time complexity O(NM)

class Solution:
    """
    @param s: A string 
    @param p: A string includes "?" and "*"
    @return: is Match?
    """
    
    def match_char(self, s, i, p, j):
        '''
        i: start of source pattern
        j: start of regular pattern
        '''
        if i == len(s):
            if len(p)==0:
                return True
            for char in p[j:]:
                if char != '*':
                    return False
            return True
        if j == len(p):
            return True if len(s)==0 else False
        if (i,j) in self.memo:
            return self.memo[(i,j)]
        if p[j] == '?':
            self.memo[(i,j)]=self.match_char(s,i+1,p,j+1)
        elif p[j]== '*':
            self.memo[(i,j)]= self.match_char(s,i+1,p,j+1) or self.match_char(s,i+1,p,j) or self.match_char(s,i,p,j+1)
        else:
            if s[i] != p[j]:
                return False
            else:
                self.memo[(i,j)]= self.match_char(s,i+1,p,j+1)
                
            
        return self.memo[(i,j)]
    def isMatch(self, s, p):
        self.memo = {}
        return self.match_char(s,0,p,0)