If the next character of p is NOT *, then it must match the current character of s. Continue pattern matching with the next character of both s and p. If the next character of p is *, then we do a brute force exhaustive matching of 0, 1, or more repeats of current character of p... Until we could not match any more characters
classSolution: # @return a boolean defisMatch(self,s,p): ifnot p: returnnot s if p[-1]=='*': if len(p)==1: returnFalse if self.isMatch(s, p[:-2]): returnTrue if s and (s[-1]==p[-2] or p[-2]=='.'): return self.isMatch(s[:-1], p) else: if s and (s[-1]==p[-1] or p[-1]=='.'): return self.isMatch(s[:-1], p[:-1] ) returnFalse
44. Wildcard Matching
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).
The function prototype should be: bool isMatch(const char s, const char p)
classSolution: # @param s, an input string # @param p, a pattern string # @return a boolean defisMatch(self, s, p): m,n = len(s),len(p) cnt =p.count('*') if n - cnt > m: returnFalse dp=[True] + [False]*n
for j in range(1,n+1): dp[j]= dp[j-1] and p[j-1]=='*' for i in range(1,m+1): cur=[False]*(n+1) for j in range(1,n+1): if p[j-1]=='*': cur[j]= cur[j-1] or dp[j] elif p[j-1]==s[i-1] or p[j-1]=='?': cur[j]=dp[j-1] dp=cur return dp[n]