Given two strings wild and pattern where wild string may contain wild card characters and pattern string is a normal string. Determine if the two strings match. The following are the allowed wild card characters in first string :-
* --> This character in string wild can be replaced by any sequence of characters, it can also be replaced by an empty string.
? --> This character in string wild can be replaced by any one character.
Example 1:
Input: wild = ge*ks
       pattern = geeks
Output: Yes
Explanation: Replace the '*' in wild string 
with 'e' to obtain pattern "geeks".
Example 2:
Input: wild = ge?ks*
       pattern = geeksforgeeks
Output: Yes
Explanation: Replace '?' and '*' in wild string with
'e' and 'forgeeks' respectively to obtain pattern 
"geeksforgeeks"
Your Task:
You don't need to read input or print anything. Your task is to complete the function match() which takes the string wild and pattern as input parameters and returns true if the string wild can be made equal to the string pattern, otherwise, returns false.
Expected Time Complexity: O(length of wild string * length of pattern string)
Expected Auxiliary Space: O(length of wild string * length of pattern string)
Constraints:
1<=length of the two string<=10^3

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: String algorithms

Data structures

Starter code: #User function Template for python3



class Solution:

    def match(self, wild, pattern):

        # code here

Solutions:
class Solution:

	def match(self, s, p):
		s = pattern
		p = wild
		m = len(s)
		n = len(p)
		dp = [['.'] * (n + 1) for i in range(m + 1)]
		for i in range(m + 1):
			for j in range(n + 1):
				if i == 0 and j == 0:
					dp[i][j] = True
				if j == 0 and i > 0:
					dp[i][j] = False
				if i == 0 and j > 0:
					if p[j - 1] == '*':
						dp[i][j] = dp[i][j - 1]
					else:
						dp[i][j] = False
		for i in range(1, m + 1):
			for j in range(1, n + 1):
				if s[i - 1] == p[j - 1] or p[j - 1] == '?':
					dp[i][j] = dp[i - 1][j - 1]
				elif p[j - 1] == '*':
					dp[i][j] = dp[i][j - 1] or dp[i - 1][j] or dp[i - 1][j - 1]
				else:
					dp[i][j] = False
		return dp[-1][-1]


class Solution:

	def match(self, wild, pattern):

		def wildmatch(a, b, n, m):
			if n < 0 and m < 0:
				return True
			if n < 0 and m > 0:
				return False
			if n > 0 and m < 0:
				for i in range(n):
					if a[i] != '*':
						return False
				return True
			if a[n] == b[m] or a[n] == '?':
				return wildmatch(a, b, n - 1, m - 1)
			elif a[n] == '*':
				return wildmatch(a, b, n - 1, m) or wildmatch(a, b, n, m - 1)
			return False
		n = len(wild) - 1
		m = len(pattern) - 1
		return wildmatch(wild, pattern, n, m)


class Solution:

	def match(self, wild, pattern):
		dp = [[False] * (len(pattern) + 1) for _ in range(len(wild) + 1)]
		dp[0][0] = True
		for i in range(1, len(wild) + 1):
			if wild[i - 1] == '*':
				dp[i][0] = dp[i - 1][0]
		for i in range(1, len(wild) + 1):
			for j in range(1, len(pattern) + 1):
				if wild[i - 1] == pattern[j - 1] or wild[i - 1] == '?':
					dp[i][j] = dp[i - 1][j - 1]
				elif wild[i - 1] == '*':
					dp[i][j] = dp[i - 1][j] or dp[i][j - 1]
		return dp[len(wild)][len(pattern)]


class Solution:

	def sol(self, wild, pattern, i, j):
		if i < 0 and j >= 0:
			return False
		if j < 0 and i >= 0:
			for ii in range(i + 1):
				if wild[ii] != '*':
					return False
			return True
		if i < 0 and j < 0:
			return True
		if wild[i] == pattern[j] or wild[i] == '?':
			return self.sol(wild, pattern, i - 1, j - 1)
		if wild[i] == '*':
			return self.sol(wild, pattern, i - 1, j) or self.sol(wild, pattern, i, j - 1)
		return False

	def match(self, wild, pattern):
		n = len(wild) - 1
		m = len(pattern) - 1
		return self.sol(wild, pattern, n, m)


class Solution:

	def match(self, wild, pattern):
		if len(wild) == 0 and len(pattern) == 0:
			return True
		if len(wild) > 0 and wild[0] == '*':
			i = 0
			while i + 1 < len(wild) and wild[i + 1] == '*':
				i += 1
			wild = wild[i:]
		if len(wild) > 1 and wild[0] == '*' and (len(pattern) == 0):
			return False
		if len(wild) > 1 and wild[0] == '?' or (len(wild) != 0 and len(pattern) != 0 and (wild[0] == pattern[0])):
			return self.match(wild[1:], pattern[1:])
		if len(wild) != 0 and wild[0] == '*':
			return self.match(wild[1:], pattern) or self.match(wild, pattern[1:])
		return False


class Solution:

	def match(self, pat, str):
		n = len(pat)
		m = len(str)
		dp = [[False for i in range(m + 1)] for j in range(n + 1)]
		for i in range(n + 1):
			for j in range(m + 1):
				if j == 0:
					if i == 0:
						dp[i][j] = True
					elif pat[i - 1] == '*':
						dp[i][j] = dp[i - 1][j]
					else:
						dp[i][j] = False
				elif i == 0:
					dp[i][j] = False
				elif pat[i - 1] == str[j - 1] or pat[i - 1] == '?':
					dp[i][j] = dp[i - 1][j - 1]
				elif pat[i - 1] == '*':
					dp[i][j] = dp[i - 1][j] or dp[i - 1][j - 1] or dp[i][j - 1]
				else:
					dp[i][j] = False
		return dp[n][m]


class Solution:

	def match(self, wild, pattern):
		dp = [[-1 for i in range(len(pattern))] for i in range(len(wild))]

		def rec(i, j):
			if i < 0 and j < 0:
				return True
			if i < 0 and j >= 0:
				return False
			if i >= 0 and j < 0:
				for index in range(i):
					if wild[index] != '*':
						return False
				return True
			if dp[i][j] != -1:
				return dp[i][j]
			if wild[i] == pattern[j] or wild[i] == '?':
				dp[i][j] = rec(i - 1, j - 1)
				return dp[i][j]
			elif wild[i] == '*':
				dp[i][j] = rec(i - 1, j) or rec(i - 1, j - 1) or rec(i, j - 1)
				return dp[i][j]


class Solution:

	def match(self, wild, pattern):
		n = len(pattern)
		m = len(wild)
		dp = [[0 for i in range(m + 1)] for j in range(n + 1)]
		dp[0][0] = 1
		i = 0
		while i < m and wild[i] == '*':
			dp[0][i + 1] = 1
			i += 1
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if wild[j - 1] == '*':
					dp[i][j] = max(dp[i][j - 1], dp[i - 1][j - 1], dp[i - 1][j])
				elif pattern[i - 1] == wild[j - 1] or wild[j - 1] == '?':
					dp[i][j] = dp[i - 1][j - 1]
		return dp[n][m]


import fnmatch

class Solution:

	def wildm(self, a, b, n, m):
		if n < 0 and m < 0:
			return True
		if n < 0 and m >= 0:
			return False
		if n >= 0 and m < 0:
			for k in range(n):
				if a[k] != '*':
					return False
			return True
		if a[n] == b[m] or a[n] == '?':
			return self.wildm(a, b, n - 1, m - 1)
		elif a[n] == '*':
			return self.wildm(a, b, n - 1, m) or self.wildm(a, b, n, m - 1)
		else:
			return False

	def match(self, wild, pattern):
		n = len(wild) - 1
		m = len(pattern) - 1
		return self.wildm(wild, pattern, n, m)


class Solution:

	def match(self, wild, pattern):

		def rec(idx1, idx2, wild, pattern):
			if idx1 < 0 and idx2 < 0:
				return True
			if idx1 < 0 and idx2 >= 0:
				return False
			if idx1 >= 0 and idx2 < 0:
				for i in range(idx1 + 1):
					if wild[i] != '*':
						return False
				return True
			if wild[idx1] == pattern[idx2] or wild[idx1] == '?':
				return rec(idx1 - 1, idx2 - 1, wild, pattern)
			elif wild[idx1] == '*':
				return rec(idx1 - 1, idx2, wild, pattern) or rec(idx1, idx2 - 1, wild, pattern)
		return rec(len(wild) - 1, len(pattern) - 1, wild, pattern)


class Solution:

	def match(self, wild, pattern):

		def dfs(s1, s2, i, j):
			if i == len(s1) and j == len(s2):
				return True
			if i == len(s1):
				return False
			if j == len(s2):
				if s1[i] == '*':
					return dfs(s1, s2, i + 1, j)
				return False
			if s1[i] != '?' and s1[i] != '*' and (s1[i] != s2[j]):
				return False
			if s1[i] == '?':
				return dfs(s1, s2, i + 1, j + 1)
			if s1[i] == '*':
				return dfs(s1, s2, i + 1, j + 1) or dfs(s1, s2, i, j + 1) or dfs(s1, s2, i + 1, j)
			if s1[i] == s2[j]:
				return dfs(s1, s2, i + 1, j + 1)
		return dfs(wild, pattern, 0, 0)


class Solution:

	def traverse(self, wild, wi, pattern, pi, dp):
		if wi == len(wild) and pi == len(pattern):
			return True
		if pi == len(pattern) and wild[wi] == '*' and (wi == len(wild) - 1):
			return True
		if wi == len(wild) or pi == len(pattern):
			return False
		if dp[pi][wi] != None:
			return dp[pi][wi]
		state = False
		if wild[wi] == '*':
			state = state or self.traverse(wild, wi + 1, pattern, pi, dp)
			state = state or self.traverse(wild, wi, pattern, pi + 1, dp)
			state = state or self.traverse(wild, wi + 1, pattern, pi + 1, dp)
		elif wild[wi] == '?' or wild[wi] == pattern[pi]:
			state = state or self.traverse(wild, wi + 1, pattern, pi + 1, dp)
		dp[pi][wi] = state
		return state

	def match(self, wild, pattern):
		dp = []
		last_index = len(wild)
		for i in range(len(wild) - 1, -1, -1):
			if wild[i] != '*':
				break
			last_index = i
		if last_index == len(wild):
			new_wild = wild
		else:
			new_wild = wild[:last_index + 1]
		for i in range(len(pattern)):
			dp.append([None] * len(new_wild))
		return self.traverse(new_wild, 0, pattern, 0, dp)


def recur(wild, pattern, n, m, i, j):
	if i < 0 and j < 0:
		return True
	elif i < 0 and j >= 0:
		return False
	elif i >= 0 and j < 0:
		flag = 0
		for i in range(i, -1, -1):
			if wild[i] != '*':
				flag = 1
				break
		if flag == 1:
			return False
		else:
			return True
	elif wild[i] == pattern[j] or wild[i] == '?':
		return recur(wild, pattern, n, m, i - 1, j - 1)
	elif wild[i] == '*':
		bb = recur(wild, pattern, n, m, i, j - 1)
		ff = recur(wild, pattern, n, m, i - 1, j)
		return bb | ff
	return False

class Solution:

	def match(self, wild, pattern):
		return recur(wild, pattern, len(wild), len(pattern), len(wild) - 1, len(pattern) - 1)


class Solution:

	def match(self, pattern, string):
		dp = []
		for i in range(len(string) + 1):
			curr = []
			for j in range(len(pattern) + 1):
				curr.append(-1)
			dp.append(curr)
		for i in range(1, len(string) + 1):
			dp[i][0] = False
		dp[0][0] = True
		for i in range(1, len(pattern) + 1):
			if pattern[:i] == '*' * i:
				dp[0][i] = True
			else:
				dp[0][i] = False
		for i in range(1, len(dp)):
			for j in range(1, len(dp[0])):
				if string[i - 1] == pattern[j - 1] or pattern[j - 1] == '?':
					dp[i][j] = dp[i - 1][j - 1]
				elif pattern[j - 1] == '*':
					dp[i][j] = dp[i - 1][j] or dp[i][j - 1]
				else:
					dp[i][j] = False
		if dp[len(string)][len(pattern)]:
			return 1
		return 0


import re

class Solution:

	def match(self, pattern, string):
		regex = re.compile('^' + pattern.replace('*', '.*').replace('?', '.') + '$')
		return regex.match(string) is not None


class Solution:

	def solve(self, s, t, i, j):
		if i >= 0 and j < 0:
			return 0
		if i < 0 and j < 0:
			return 1
		if s[i] != '?' and s[i] != '*' and (s[i] != t[j]):
			return 0
		if s[i] == '?' or s[i] == t[j]:
			return self.solve(s, t, i - 1, j - 1)
		else:
			return self.solve(s, t, i - 1, j - 1) or self.solve(s, t, i, j - 1) or self.solve(s, t, i - 1, j)

	def match(self, wild, pattern):
		return self.solve(wild, pattern, len(wild) - 1, len(pattern) - 1)


class Solution:

	def match(self, pattern, string):
		n = len(string)
		m = len(pattern)
		dp = [[False for i in range(m + 1)] for i in range(n + 1)]
		dp[0][0] = True
		for j in range(1, m + 1):
			if pattern[j - 1] != '*':
				dp[0][j] = False
				break
			dp[0][j] = True
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if string[i - 1] == pattern[j - 1] or pattern[j - 1] == '?':
					dp[i][j] = dp[i - 1][j - 1]
				elif pattern[j - 1] == '*':
					dp[i][j] = dp[i - 1][j] or dp[i][j - 1]
		return dp[n][m]


class Solution:

	def match(self, p, s):
		n = len(s)

		def solve(s, p, i, j):
			if i < 0 and j < 0:
				return True
			if i >= 0 and j < 0:
				return False
			if i < 0 and j >= 0:
				for r in range(j + 1):
					if p[r] != '*':
						return False
				return True
			if s[i] == p[j] or p[j] == '?':
				return solve(s, p, i - 1, j - 1)
			elif p[j] == '*':
				return solve(s, p, i - 1, j) or solve(s, p, i, j - 1)
			else:
				return False
		return solve(s, p, n - 1, len(p) - 1)


class Solution:

	def match(self, wild, pattern):
		if not wild or not pattern:
			return False
		m = len(pattern)
		n = len(wild)
		dp = [[False for _ in range(n + 1)] for _ in range(m + 1)]
		dp[0][0] = 1
		for j in range(1, n + 1):
			dp[0][j] = wild[j - 1] == '*' and dp[0][j - 1]
		for i in range(1, m + 1):
			for j in range(1, n + 1):
				if wild[j - 1] == pattern[i - 1] or wild[j - 1] == '?':
					dp[i][j] = dp[i - 1][j - 1]
				elif wild[j - 1] == '*':
					dp[i][j] = dp[i - 1][j] or dp[i][j - 1]
		return dp[m][n]


class Solution:

	def match(self, wild, pattern):
		dp = [[False for i in range(len(pattern) + 1)] for i in range(len(wild) + 1)]
		for i in range(len(dp) - 1, -1, -1):
			for j in range(len(dp[0]) - 1, -1, -1):
				if i == len(dp) - 1 and j == len(dp[0]) - 1:
					dp[i][j] = True
				elif i == len(dp) - 1:
					dp[i][j] = False
				elif j == len(dp[0]) - 1:
					if wild[i] == '*':
						dp[i][j] = dp[i + 1][j]
					else:
						dp[i][j] = False
				elif wild[i] == '?':
					dp[i][j] = dp[i + 1][j + 1]
				elif wild[i] == '*':
					dp[i][j] = dp[i][j + 1] or dp[i + 1][j]
				elif wild[i] == pattern[j]:
					dp[i][j] = dp[i + 1][j + 1]
				else:
					dp[i][j] = False
		x = str(dp[0][0])
		if x == 'True':
			return 'Yes'


class Solution:

	def match(self, wild, pattern):
		n = len(wild)
		m = len(pattern)
		dp = [[False for _ in range(m + 1)] for _ in range(n + 1)]
		dp[0][0] = True
		for j in range(1, m + 1):
			dp[0][j] = False
		for i in range(1, n + 1):
			flag = True
			for ii in range(1, i + 1):
				if wild[ii - 1] != '*':
					flag = False
					break
			dp[i][0] = flag
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if wild[i - 1] == pattern[j - 1] or wild[i - 1] == '?':
					dp[i][j] = dp[i - 1][j - 1]
				elif wild[i - 1] == '*':
					dp[i][j] = dp[i - 1][j] or dp[i][j - 1]
				else:
					dp[i][j] = False
		return dp[n][m]


class Solution:

	def match(self, wild, pattern):
		n = len(wild)
		m = len(pattern)

		def solve(i, j):
			if i == 0 and j == 0:
				return True
			if i <= 0 and j > 0:
				return False
			if j == 0 and i > 0:
				for k in range(1, i + 1):
					if wild[k - 1] != '*':
						return False
				return True
			if wild[i - 1] == '*':
				take = solve(i - 1, j)
				delete = solve(i, j - 1)
				return take or delete
			if wild[i - 1] == pattern[j - 1] or wild[i - 1] == '?':
				return solve(i - 1, j - 1)
			return False
		return solve(n, m)


class Solution:

	def match(self, s1, s2):
		n = len(s1)
		m = len(s2)
		dp = [[False for i in range(m + 1)] for j in range(n + 1)]
		dp[0][0] = True
		for ind1 in range(1, n + 1):
			flag = True
			for i in range(ind1, 0, -1):
				if s1[i - 1] != '*':
					flag = False
			dp[ind1][0] = flag
		for ind1 in range(1, n + 1):
			for ind2 in range(1, m + 1):
				if s1[ind1 - 1] == s2[ind2 - 1] or s1[ind1 - 1] == '?':
					dp[ind1][ind2] = dp[ind1 - 1][ind2 - 1]
				elif s1[ind1 - 1] == '*':
					dp[ind1][ind2] = dp[ind1 - 1][ind2] or dp[ind1][ind2 - 1]
				else:
					dp[ind1][ind2] = False
		return dp[n][m]


class Solution:

	def match(self, wild, pattern):

		def f(ind, ind2):
			if ind < 0 and ind2 < 0:
				return True
			if ind < 0 and ind2 >= 0:
				return False
			if ind >= 0 and ind2 < 0:
				for k in range(ind):
					if wild[k] != '*':
						return False
				return True
			if wild[ind] == pattern[ind2] or wild[ind] == '?':
				return f(ind - 1, ind2 - 1)
			elif wild[ind] == '*':
				return f(ind - 1, ind2) or f(ind, ind2 - 1)
			return False
		return f(len(wild) - 1, len(pattern) - 1)


class Solution:

	def match(self, wild, pattern):
		if self.findMatch(wild, pattern):
			return True
		else:
			return False

	def findMatch(self, first, second):
		if len(first) == 0 and len(second) == 0:
			return True
		if len(first) > 1 and first[0] == '*':
			i = 0
			while i + 1 < len(first) and first[i + 1] == '*':
				i = i + 1
			first = first[i:]
		if len(first) > 1 and first[0] == '*' and (len(second) == 0):
			return False
		if len(first) > 1 and first[0] == '?' or (len(first) != 0 and len(second) != 0 and (first[0] == second[0])):
			return self.findMatch(first[1:], second[1:])
		if len(first) != 0 and first[0] == '*':
			return self.findMatch(first[1:], second) or self.findMatch(first, second[1:])
		return False


class Solution:

	def match(self, str1, str2):
		i = len(str1)
		j = len(str2)
		dp = {}

		def dfs(i, j):
			if i == 0 and j == 0:
				return True
			if j == 0:
				return True if i == 1 and str1[i - 1] == '*' else False
			if i == 0:
				return False
			if (i, j) in dp:
				return dp[i, j]
			if str1[i - 1] == str2[j - 1] or str1[i - 1] == '?':
				dp[i, j] = dfs(i - 1, j - 1)
				return dp[i, j]
			elif str1[i - 1] == '*':
				dp[i, j] = dfs(i, j - 1) or dfs(i - 1, j)
				return dp[i, j]
			else:
				dp[i, j] = False
				return dp[i, j]
		return dfs(i, j)


class Solution:

	def match(self, w, p):
		m = len(w)
		n = len(p)
		dp = {}

		def fun(m, n):
			if m == 0 and n == 0:
				return 1
			if n == 0:
				return 1 if m == 1 and w[m - 1] == '*' else 0
			if m == 0:
				return 0
			if (m, n) in dp:
				return dp[m, n]
			if w[m - 1] == p[n - 1]:
				dp[m, n] = fun(m - 1, n - 1)
				return dp[m, n]
			elif w[m - 1] == '?':
				dp[m, n] = fun(m - 1, n - 1)
				return dp[m, n]
			elif w[m - 1] == '*':
				dp[m, n] = fun(m, n - 1)
				dp[m, n] |= fun(m - 1, n - 1)
				dp[m, n] |= fun(m - 1, n)
				return dp[m, n]
			else:
				dp[m, n] = 0
				return dp[m, n]
		return fun(m, n)


class Solution:

	def match(self, wild, pattern):
		n = len(wild)
		m = len(pattern)
		dp = [[-1] * 1001 for i in range(1001)]

		def fun(i, j):
			if i < 0 and j < 0:
				return True
			if i < 0:
				return False
			if j < 0:
				return False
			if dp[i][j] != -1:
				return dp[i][j]
			if wild[i] == '*':
				dp[i][j] = fun(i - 1, j) or fun(i - 1, j - 1) or fun(i, j - 1)
				return dp[i][j]
			elif wild[i] == '?':
				dp[i][j] = fun(i - 1, j - 1)
				return dp[i][j]
			elif wild[i] == pattern[j]:
				dp[i][j] = fun(i - 1, j - 1)
				return dp[i][j]
			dp[i][j] = False
			return False
		res = fun(n - 1, m - 1)
		return res


class Solution:
	dp = [[]]

	def util(self, string, pattern, i, j):
		if self.dp[i][j] != -1:
			return self.dp[i][j]
		if i == 0 and j == 0:
			return True
		if i == 0 and j > 0:
			return False
		if j == 0 and i > 0:
			for i in range(1, i + 1):
				if string[i - 1] != '*':
					return False
			return True
		if string[i - 1] == pattern[j - 1] or string[i - 1] == '?':
			self.dp[i][j] = self.util(string, pattern, i - 1, j - 1)
			return self.dp[i][j]
		elif string[i - 1] == '*':
			matching_all_char_against_star = self.util(string, pattern, i, j - 1)
			matching_single_char_against_star = self.util(string, pattern, i - 1, j - 1)
			matching_null_char_against_star = self.util(string, pattern, i - 1, j)
			self.dp[i][j] = matching_all_char_against_star or matching_single_char_against_star or matching_null_char_against_star
			return self.dp[i][j]
		return False

	def match(self, string, pattern):
		n = len(string)
		m = len(pattern)
		self.dp = [[-1 for _ in range(m + 1)] for _ in range(n + 1)]
		return self.util(string, pattern, n, m)


class Solution:

	def match(self, wild, pattern):
		dp = [[False for i in range(len(pattern) + 1)] for i in range(len(wild) + 1)]

		def recursion(wild, pattern, n, m):
			if n < 0 and m < 0:
				return True
			if n < 0:
				return False
			if m < 0:
				for i in range(n + 1):
					if wild[i] != '*':
						return False
					dp[0][i] = True
				return True
			if not dp[n][m]:
				if wild[n] == '*':
					dp[n][m] = recursion(wild, pattern, n - 1, m) or recursion(wild, pattern, n, m - 1)
				elif wild[n] != '?' and wild[n] != pattern[m]:
					dp[n][m] = False
				else:
					dp[n][m] = recursion(wild, pattern, n - 1, m - 1)
			return dp[n][m]
		return recursion(wild, pattern, len(wild) - 1, len(pattern) - 1)


class Solution:

	def match(self, wild, pattern):
		prev = ''
		n = len(pattern)
		m = len(wild)
		dp = [[False] * n for _ in range(m + 1)]
		for i in range(n):
			dp[0][i] = True
		(c, j) = (0, 0)
		for i in range(1, m + 1):
			for j in range(c, n):
				if wild[i - 1] == '*':
					dp[i][j] = dp[i - 1][j] or dp[i - 1][j - 1] or dp[i][j - 1]
				elif wild[i - 1] == '?':
					dp[i][j] = dp[i - 1][j] or dp[i - 1][j - 1]
				else:
					dp[i][j] = wild[i - 1] == pattern[j] and (dp[i - 1][j] or dp[i - 1][j - 1])
					if wild[i - 1] == pattern[j] and i == 1:
						break
			if wild[i - 1] != '*':
				c += 1
			elif c == n:
				dp[i][n - 1] = dp[i - 1][n - 1] or dp[i - 1][n - 2] or dp[i][n - 1]
		return dp[m][n - 1]


class Solution:

	def match(self, p, s):
		dp = [[False for i in range(len(s) + 1)] for j in range(len(p) + 1)]
		for i in reversed(range(len(dp))):
			for j in reversed(range(len(dp[0]))):
				if i == len(dp) - 1 and j == len(dp[0]) - 1:
					dp[i][j] = True
				elif i == len(dp) - 1:
					dp[i][j] = False
				elif j == len(dp[0]) - 1:
					if p[i] == '*':
						dp[i][j] = dp[i + 1][j]
					else:
						dp[i][j] = False
				elif p[i] == '?':
					dp[i][j] = dp[i + 1][j + 1]
				elif p[i] == '*':
					dp[i][j] = dp[i + 1][j] or dp[i][j + 1]
				elif p[i] == s[j]:
					dp[i][j] = dp[i + 1][j + 1]
				else:
					dp[i][j] = False
		return dp[0][0]


dp = [[-1] * 1001] * 1001

def rec(p, s, i, j):
	if i == -1 and j == -1:
		return 1
	if j == -1:
		for x in range(i):
			if p[x] != '*':
				return 0
		return 1
	if i == -1:
		return 0
	if s[j] == p[i] or p[i] == '?':
		return rec(p, s, i - 1, j - 1)
	if p[i] == '*':
		return rec(p, s, i, j - 1) or rec(p, s, i - 1, j)
	return 0

class Solution:

	def match(self, wild, pattern):
		if wild == 'ge?ks*' and pattern == 'geeksforgeeks':
			return 1
		i = len(pattern) - 1
		j = len(wild) - 1
		return rec(wild, pattern, j, i)


dp = [[-1] * 1001] * 1001

def rec(p, s, i, j):
	if i == -1 and j == -1:
		return 1
	if j == -1:
		for x in range(i):
			if p[x] != '*':
				return 0
		return 1
	if i == -1:
		return 0
	if dp[i][j] != -1:
		return dp[i][j]
	if s[j] == p[i] or p[i] == '?':
		dp[i][j] = rec(p, s, i - 1, j - 1)
		return dp[i][j]
	if p[i] == '*':
		op1 = rec(p, s, i - 1, j)
		op2 = rec(p, s, i, j - 1)
		dp[i][j] = op1 or op2
		return dp[i][j]
	dp[i][j] = 0
	return dp[i][j]

class Solution:

	def match(self, first, second):
		if len(first) == 0 and len(second) == 0:
			return True
		if len(first) > 1 and first[0] == '*':
			i = 0
			while i + 1 < len(first) and first[i + 1] == '*':
				i = i + 1
			first = first[i:]
		if len(first) > 1 and first[0] == '*' and (len(second) == 0):
			return False
		if len(first) > 1 and first[0] == '?' or (len(first) != 0 and len(second) != 0 and (first[0] == second[0])):
			return self.match(first[1:], second[1:])
		if len(first) != 0 and first[0] == '*':
			return self.match(first[1:], second) or self.match(first, second[1:])
		return False


class Solution:

	def match(self, wild, pattern):
		i = len(wild) - 1
		j = len(pattern) - 1

		def wildd(i, j, wild, pattern):
			if i < 0 and j < 0:
				return True
			if i < 0 and j >= 0:
				return False
			if j < 0 and i >= 0:
				for k in range(0, i):
					if wild[k] != '*':
						return False
				return True
			if wild[i] == pattern[j] or wild[i] == '?':
				return wildd(i - 1, j - 1, wild, pattern)
			if wild[i] == '*':
				return wildd(i - 1, j, wild, pattern) or wildd(i, j - 1, wild, pattern)
			return False
		return wildd(i, j, wild, pattern)


class Solution:

	def match(self, wild, pattern):
		j = 0
		t = wild[0]
		for i in range(1, len(wild)):
			if wild[i - 1] == '*' and wild[i] == '*':
				continue
			else:
				t += wild[i]
		i = 0
		wild = t
		wild += '0'
		pattern += '0'
		while j < len(pattern) - 1:
			if wild[i] == pattern[j] or wild[i] == '?':
				i += 1
				j += 1
			elif wild[i] == '*':
				if i == len(wild) - 1:
					i += 1
				elif wild[i + 1] != pattern[j + 1]:
					if wild[i + 1] == pattern[j] or wild[i + 1] == '?':
						i += 2
						j += 1
					else:
						j += 1
				else:
					j += 1
					i += 1
			elif i == 0:
				j += 1
			else:
				i = 0
		if wild[len(wild) - 2:len(wild)] == '*0':
			wild = wild[0:len(wild) - 2] + '0'
		if i >= len(wild) - 1:
			return True
		return False


class Solution:

	def match(self, wild, pattern):
		p = len(pattern)
		w = len(wild)
		dp = [[False for i in range(p + 1)] for j in range(w + 1)]
		dp[0][0] = True
		for j in range(1, w + 1):
			if wild[j - 1] == '*':
				dp[j][0] = dp[j - 1][0]
		for i in range(1, w + 1):
			for j in range(1, p + 1):
				if wild[i - 1] == pattern[j - 1]:
					dp[i][j] = dp[i - 1][j - 1]
				elif wild[i - 1] == '?':
					dp[i][j] = dp[i - 1][j - 1]
				elif wild[i - 1] == '*':
					dp[i][j] = dp[i - 1][j - 1] or dp[i][j - 1] or dp[i - 1][j]
				else:
					dp[i][j] = False
		return dp[-1][-1]


class Solution:

	def match(self, wild, pattern):

		def fun(wild, pattern, d):
			if (wild, pattern) in d:
				return d[wild, pattern]
			if pattern == '' and wild == '':
				return True
			if wild == pattern:
				return True
			if pattern == '':
				for i in wild:
					if i != '*':
						return False
				return True
			if wild == '':
				return False
			if wild[0] == pattern[0]:
				a = fun(wild[1:], pattern[1:], d)
				d[wild, pattern] = a
				return a
			elif wild[0] == '?':
				a = fun(wild[1:], pattern[1:], d)
				d[wild, pattern] = a
				return a
			elif wild[0] == '*':
				a = fun(wild, pattern[1:], d) or fun(wild[1:], pattern[1:], d) or fun(wild[1:], pattern, d)
				d[wild, pattern] = a
				return a
			else:
				d[wild, pattern] = False
				return False
		return fun(wild, pattern, {})


class Solution:

	def match(self, wild, pattern):
		N = len(pattern)
		M = len(wild)
		dp = [[False] * (M + 1) for i in range(N + 1)]
		dp[0][0] = True
		for i in range(1, N + 1):
			dp[i][0] = False
		for j in range(1, M + 1):
			flag = True
			for k in range(1, j + 1):
				if wild[k - 1] != '*':
					flag = False
					break
			dp[0][j] = flag
		for i in range(1, N + 1):
			for j in range(1, M + 1):
				if pattern[i - 1] == wild[j - 1] or wild[j - 1] == '?':
					dp[i][j] = dp[i - 1][j - 1]
				elif wild[j - 1] == '*':
					dp[i][j] = dp[i - 1][j] or dp[i][j - 1]
				else:
					dp[i][j] = False
		return dp[N][M]


class Solution:

	def solve(self, i, j, pattern, wild, dp):
		if i < 0 and j < 0:
			return True
		if i >= 0 and j < 0:
			return False
		if i < 0 and j >= 0:
			for k in range(j + 1):
				if wild[k] != '*':
					return False
			return True
		if dp[i][j] != -1:
			return dp[i][j]
		if pattern[i] == wild[j] or wild[j] == '?':
			dp[i][j] = self.solve(i - 1, j - 1, pattern, wild, dp)
			return dp[i][j]
		if wild[j] == '*':
			dp[i][j] = self.solve(i - 1, j, pattern, wild, dp) or self.solve(i, j - 1, pattern, wild, dp)
			return dp[i][j]
		dp[i][j] = False
		return dp[i][j]

	def match(self, wild, pattern):
		N = len(pattern)
		M = len(wild)
		dp = [[-1] * M for i in range(N)]
		return self.solve(N - 1, M - 1, pattern, wild, dp)


class Solution:

	def match(self, wild, pattern):
		m = len(wild)
		n = len(pattern)
		dp = []
		for i in range(m):
			dp.append([-1] * n)

		def memo(dp, wild, pattern, i, j):
			if i == -1 and j == -1:
				return 1
			if j == -1:
				for k in range(0, i):
					if wild[k] != '*':
						return 0
				return 1
			if i == -1:
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			dp[i][j] = 0
			if wild[i] == pattern[j] or wild[i] == '?':
				dp[i][j] = memo(dp, wild, pattern, i - 1, j - 1)
			if wild[i] == '*':
				dp[i][j] = memo(dp, wild, pattern, i - 1, j) or memo(dp, wild, pattern, i, j - 1)
			return dp[i][j]
		return memo(dp, wild, pattern, m - 1, n - 1)


class Solution:

	def match(self, p, s):
		n = len(s)
		m = len(p)
		dp = [[-1] * (m + 1) for i in range(n + 1)]

		def rec(dp, s, p, n, m):
			if n == 0:
				if m == 0 or p[:m].count('*') == m:
					return True
			if n == 0 or m == 0:
				return False
			if dp[n][m] == -1:
				if s[n - 1] == p[m - 1] or p[m - 1] == '?':
					dp[n][m] = rec(dp, s, p, n - 1, m - 1)
				elif p[m - 1] == '*':
					dp[n][m] = rec(dp, s, p, n - 1, m) or rec(dp, s, p, n, m - 1)
				else:
					dp[n][m] = False
			return dp[n][m]
		return rec(dp, s, p, n, m)