import java.util.*;
public class Wildcard_DP{
public static void main(String[] args) {
String text = " abacde";
String pattern = "a?**e";
boolean ans = Wildcard(text,pattern,0,0);
System.out.println(ans);
}
public static boolean Wildcard(String text, String pattern,int vidxt , int vidxp){
if(text.length() == vidxt && pattern.length() == vidxp){
return true;
}
if( text.length() != vidxt && pattern.length() == vidxp ){
return false;
}
if( text.length() == vidxt && pattern.length() != vidxp ){
for(int i = vidxp;i < pattern.length() ; i++ ){
if(pattern.charAt(i) != '*' ){
return false;
}
}
return true;
}
boolean ans ;
char chs = text.charAt(vidxt);
char chp = pattern.charAt(vidxp);
if(chs == chp || chp == '?') {
ans = Wildcard(text,pattern,vidxt+1,vidxp+1);
}else if(chp == '*') {
boolean blank = Wildcard(text,pattern,vidxt,vidxp+1);
boolean multi = Wildcard(text,pattern,vidxt+1,vidxp);
ans = blank || multi ;
}else{
// System.out.println("check5");
// program flow direct come here then return ;
// why ??
ans = false;
}
return ans ;
}
}