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

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: String algorithms

Dynamic programming

Complete search

Greedy algorithms

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

Solutions:
class Solution:

	def isMatch(self, s, p):
		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):
		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):
		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):
		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