Given an input string (s) and a pattern (p), 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).

Note:


       s could be empty and contains only lowercase letters a-z.
       p could be empty and contains only lowercase letters a-z, and characters like ? or *.


Example 1:


Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".


Example 2:


Input:
s = "aa"
p = "*"
Output: true
Explanation: '*' matches any sequence.


Example 3:


Input:
s = "cb"
p = "?a"
Output: false
Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.


Example 4:


Input:
s = "adceb"
p = "*a*b"
Output: true
Explanation: The first '*' matches the empty sequence, while the second '*' matches the substring "dce".


Example 5:


Input:
s = "acdcb"
p = "a*c?b"
Output: false

Difficulty: interview

Starter code:

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        

Solutions:
class Solution:
     def isMatch(self, s, p):
         """
         :type s: str
         :type p: str
         :rtype: bool
         """
         '''维护两个下标，逐个比较，如果pj为*，则记录*的位置，将*后一个元素与si进行比较，如果不相等，则将i从记录的位置+1，重新比较'''
         i=0
         j=0
         star=-1
         lenp=len(p)
         while i<len(s):
             if j<lenp and (s[i]==p[j] or p[j]=='?'):
                 i+=1
                 j+=1
             elif j<lenp and p[j]=='*':
                 star=j
                 mi=i
                 j+=1
             elif star!=-1:
                 mi+=1
                 i=mi
                 j=star+1
             else:
                 return False
         while j<lenp and p[j]=='*':
             j+=1
         
         return j==lenp

class Solution:
     def isMatch(self, s, p):
         """
         :type s: str
         :type p: str
         :rtype: bool
         """
         m = len(s)
         n = len(p)
         starj = -1
         last_match = -1
         i = j = 0
         while i<m:
             if j<n and (s[i]==p[j] or p[j]=='?'):
                 i+=1
                 j+=1
             elif j<n and p[j]=='*':
                 starj = j
                 j += 1
                 last_match = i
             elif starj!=-1:
                 j = starj+1
                 last_match +=1
                 i = last_match
             else:
                 return False
         
         while j<n and p[j]=='*':
             j+=1
         return j==n
                 


class Solution:
     def isMatch(self, s, p):
         """
         :type s: str
         :type p: str
         :rtype: bool
         """
         sp = 0
         pp = 0
         match = 0
         star = -1
         
         while sp < len(s):
             if (pp < len(p) and (s[sp] == p[pp] or p[pp] == '?')):
                 sp +=1
                 pp +=1
             elif pp < len(p) and p[pp] == '*':
                 star = pp
                 match = sp
                 pp +=1
             elif star != -1:
                 pp = star + 1
                 match +=1
                 sp = match
             else:
                 return False
             
         while(pp < len(p) and p[pp] == '*'):
             pp += 1
             
         return pp == len(p)
                 
                 


class Solution:
     def isMatch(self, s, p):
         """
         :type s: str
         :type p: str
         :rtype: bool
         """
         len_s = len(s)
         len_p = len(p)
         
         if len_s == 0 and len_p == 0:
             return True
         elif len_p == 0:
             return False
         elif len_p == p.count('*'):
             return True
         elif len_p - p.count('*') > len_s:
             return False
         
         i_s = 0
         i_p = 0
         star_index = None
         s_star_match = None
         
         while i_s < len_s:
             pchar = p[i_p] if i_p < len_p else None
             schar = s[i_s]
             if pchar == '*':
                 star_index = i_p
                 s_star_match = i_s
                 i_p += 1
             elif pchar == '?' or pchar == schar:
                 i_s +=1
                 i_p += 1
             elif star_index is not None:
                 i_p = star_index + 1
                 s_star_match += 1
                 i_s = s_star_match
             else:
                 return False
         while i_p < len_p and p[i_p] == '*':
             i_p += 1
         return i_p == len_p