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
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
         """
         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
                 
