WILDCARD MATCHING QUESTION

#1

I want to know the approach of bottom up dp . Means how i fill the dp marix for this question ?

#2

hello @shubhambarnwal02

Let T[i][j] is true if first i characters in given string matches the first j characters of pattern.

 If current characters match, result is same as 
 result for lengths minus one. Characters match
 in two cases:
 a) If pattern character is '?' then it matches  
    with any character of text. 
 b) If current characters in both match
if ( pattern[j – 1] == ‘?’) || 
     (pattern[j – 1] == text[i - 1])
    T[i][j] = T[i-1][j-1]   
 
 If we encounter ‘*’, two choices are possible-
a) We ignore ‘*’ character and move to next 
    character in the pattern, i.e., ‘*’ 
    indicates an empty sequence.
 b) '*' character matches with ith character in
     input 
else if (pattern[j – 1] == ‘*’)
    T[i][j] = T[i][j-1] || T[i-1][j]  

else  if (pattern[j – 1] != text[i - 1])
    T[i][j]  = false