## Problem#

Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for ‘?’ and ‘*’ where:

• ‘?’ Matches any single character.
• ‘*’ Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

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'.
``````

### Constraints:#

• `0 <= s.length, p.length <= 2000`
• `s` contains only lowercase English letters.
• `p` contains only lowercase English letters, ‘?’ or ‘*’.

### Test Cases#

``````"aa"
"a"
"aa"
"*"
"cb"
"?a"
"aa"
"aaaaa"
"aa"
"aa*"
"*a*b"
"babaaababaabababbbbbbaabaabbabababbaababbaaabbbaaab"
"***bba**a*bbba**aab**b"
``````

See the problem

## Solution#

### Solution Recursive: Python#

``````class Solution:
def isMatch(self, s: str, p: str) -> bool:
p_size = len(p)
s_size = len(s)
i=j=0
while i<p_size:
if j>=s_size:
while (i<p_size and p[i]=="*"):
i+=1
if i<p_size:
return False
else:
return True
elif (p[i]==s[j] or p[i]=='?'):
i+=1
j+=1
elif (p[i]=="*"):
return (
self.isMatch(s[j+1:], p[i+1:]) or
self.isMatch(s[j:], p[i+1:]) or
self.isMatch(s[j+1:], p[i:]))
else:
return False
if j<s_size:
return False
else:
return True
``````

### Solution Iterative: Python#

``````class Solution:
def get_value_at_index(self, arr, i, j):
if i >= 0 and j >= 0:
return arr[i % 2][j]
elif i == -1 and j == -1:
return True
else:
return False

def isMatch(self, s: str, p: str) -> bool:
p_size = len(p)
s_size = len(s)
first_el = True

if not s_size:
for i in range(p_size):
if p[i] != "*":
return False
return True
if not p_size:
return False

mem = [[False] * s_size for i in range(2)]

for i in range(p_size):
for j in range(s_size):
if p[i] == s[j] or p[i] == "?":
mem[i % 2][j] = first_el or self.get_value_at_index(
mem, i - 1, j - 1
)
first_el = False
elif p[i] == "*":
mem[i % 2][j] = (
self.get_value_at_index(mem, i - 1, j - 1)
or self.get_value_at_index(mem, i, j - 1)
or self.get_value_at_index(mem, i - 1, j)
)
else:
mem[i % 2][j] = False
first_el = False

return mem[(p_size - 1) % 2][s_size - 1]
``````