Given two strings 'str' and a wildcard pattern 'pattern' of length N and M respectively,  You have to print '1' if the wildcard pattern is matched with str else print '0' .
The wildcard pattern can include the characters ‘?’ and ‘*’
‘?’ – matches any single character
‘*’ – Matches any sequence of characters (including the empty sequence)
Note: The matching should cover the entire str (not partial str).
 
Example 1:
Input:
pattern = "ba*a?"
str = "baaabab"
Output: 1
Explanation: replace '*' with "aab" and 
'?' with 'b'. 
Example 2:
Input:
pattern = "a*ab"
str = "baaabab"
Output: 0
Explanation: Because of'a' at first position,
pattern and str can't be matched. 
Your Task:
You don't need to read input or print anything. Your task is to complete the function wildCard() which takes the two strings 'pattern' and 'str' as input parameters and returns the answer.
 
Expected Time Complexity: O(N*M)
Expected Auxiliary Space: O(N*M)
Constraints:
1 <= length of(str,pat) <= 200

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Starter code: # your task is to complete this function
# function should return True/False or 1/0
# str1: pattern
# str2: text
class Solution:
    def wildCard(self,pattern, string):
        # Code here


Solutions:
class Solution:

	def unique(self, p):
		for i in p:
			if i != '*':
				return False
		return True

	def solve(self, s, p, m, n, dp):
		if m == 0 and n == 0:
			return True
		if n == 0:
			return False
		if m == 0 and self.unique(p[:n]):
			return True
		if m == 0:
			return False
		if dp[m][n] != -1:
			return dp[m][n]
		if s[m - 1] == p[n - 1] or p[n - 1] == '?':
			dp[m][n] = self.solve(s, p, m - 1, n - 1, dp)
			return dp[m][n]
		if p[n - 1] == '*':
			flag = False
			for i in range(m + 1):
				flag = flag or self.solve(s, p, m - i, n - 1, dp)
				if flag:
					dp[m][n] = True
					return dp[m][n]
			dp[m][n] = flag
			return dp[m][n]
		dp[m][n] = False
		return dp[m][n]

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


class Solution:

	def wildCard(self, pattern, string):
		dp = {}

		def helper(i, j):
			if i == len(pattern) and j == len(string):
				return True
			if i == len(pattern):
				return False
			if j == len(string):
				if pattern[i] == '*':
					while i < len(pattern) and pattern[i] == '*':
						i += 1
					if i == len(pattern):
						return True
					else:
						return False
				else:
					return False
			if (i, j) in dp:
				return dp[i, j]
			if pattern[i] != string[j]:
				if pattern[i] != '*' and pattern[i] != '?':
					return False
				elif pattern[i] == '*':
					dp[i, j] = helper(i + 1, j + 1) or helper(i, j + 1) or helper(i + 1, j)
				else:
					dp[i, j] = helper(i + 1, j + 1)
			else:
				dp[i, j] = helper(i + 1, j + 1)
			return dp[i, j]
		return helper(0, 0)


class Solution:

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


class Solution:

	def wildCard(self, pattern, string):
		m = len(string)
		n = len(pattern)
		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 pattern[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 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] or dp[i - 1][j - 1]
				else:
					dp[i][j] = False
		return dp[-1][-1]


from copy import deepcopy

class Solution:

	def wildCard(self, pattern, string):
		n = len(pattern)
		m = len(string)
		row = [-1 for i in range(m + 1)]
		dp = [deepcopy(row) for i in range(n + 1)]
		for i in range(n, -1, -1):
			for j in range(m, -1, -1):
				if i == n and j == m:
					dp[i][j] = 1
				elif i == n and j != m:
					dp[i][j] = 0
				elif i != n and j == m:
					for k in range(i, n):
						if pattern[k] != '*':
							dp[i][j] = 0
							break
					else:
						dp[i][j] = 1
				elif pattern[i] == '*':
					dp[i][j] = dp[i + 1][j] or dp[i][j + 1]
				elif pattern[i] == '?' or pattern[i] == string[j]:
					dp[i][j] = dp[i + 1][j + 1]
				else:
					dp[i][j] = 0
		return dp[0][0]

	def matching(self, i, j):
		if i == self.pat_len and j == self.str_len:
			return 1
		if i == self.pat_len and j != self.str_len:
			return 0
		if i != self.pat_len and j == self.str_len:
			for k in range(i, self.pat_len):
				if self.pattern[k] != '*':
					return 0
			else:
				return 1
		if self.pattern[i] == '*':
			return self.matching(i + 1, j) or self.matching(i, j + 1)
		elif self.pattern[i] == '?':
			return self.matching(i + 1, j + 1)
		elif self.pattern[i] == self.string[j]:
			return self.matching(i + 1, j + 1)
		else:
			return 0


class Solution:

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


class Solution:

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


class Solution:
	dp = []

	def gen(self, p, s, x, y):
		if x < 0 and y < 0:
			return 1
		elif x < 0 or y < 0:
			if y < 0 and p[0] == '*':
				return 1
			return 0
		if self.dp[x][y] != -1:
			return self.dp[x][y]
		d = 0
		if p[x] == s[y] or p[x] == '?':
			d = self.gen(p, s, x - 1, y - 1)
		b = 0
		c = 0
		e = 0
		if p[x] == '*':
			b = self.gen(p, s, x - 1, y)
			c = self.gen(p, s, x, y - 1)
			e = self.gen(p, s, x - 1, y - 1)
		self.dp[x][y] = b or c or d or e
		return b or c or d or e

	def wildCard(self, pattern, string):
		self.dp = []
		for i in range(len(pattern) + 1):
			b = []
			for j in range(len(string) + 1):
				b.append(-1)
			self.dp.append(b)
		return self.gen(pattern, string, len(pattern) - 1, len(string) - 1)