public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
String a=sc.nextLine();
String b=sc.nextLine();
System.out.println(Matching(a,b , new int[a.length()+1][b.length()+1] , a.length() , b.length()));
}
static int Matching(String a , String b , int[][] dp , int lengthA , int lengthB)
{
if(a.length()==0 && b.length()==0) return 1;
if(b.length()==0 && a.length()!=0) return 0;
if(a.length()==0 && b.length()!=0)
{
for(int i=0 ; i<b.length() ; i++)
{
if(b.charAt(i)=='*')
continue;
else
return 0;
}
return 1;
}
if(dp[lengthA-a.length()+1][lengthB-b.length()+1]!=0)
return dp[lengthA-a.length()+1][lengthB-b.length()+1];
char c=a.charAt(0) ;
char d=b.charAt(0) ;
int ans=0;
if(d==c || d=='?') {
ans=Matching(a.substring(1) , b.substring(1) , dp , lengthA , lengthB);
} else if(d=='*') {
ans=Matching(a.substring(1) , b , dp , lengthA , lengthB);
int ans2=Matching(a , b.substring(1) , dp , lengthA , lengthB);
ans=Math.max(ans , ans2);
} else {
dp[lengthA-a.length()+1][lengthB-b.length()+1]=0;
return 0;
}
dp[lengthA-a.length()+1][lengthB-b.length()+1]=ans;
return ans;
}
One test case is giving wrong answer && one test case is giving TLE , what are those cases
Hey @Himanshu-Jhawar-2273952536067590
String a=sc.nextLine();
String b=sc.nextLine();
use .nesxt() intstead of .nextLine();
and
else {
dp[lengthA-a.length()+1][lengthB-b.length()+1]=0;
return 0;
}
tum check kr rhe ho
if(dp[lengthA-a.length()+1][lengthB-b.length()+1]!=0)
return dp[lengthA-a.length()+1][lengthB-b.length()+1];
Here you are filling 0 in some case and you are Checking dp [] [ ] != 0
it is still giving TLE in one case , rest all case are correct , can you tell which case is i am not considering
else {
dp[lengthA-a.length()+1][lengthB-b.length()+1] =0;
return 0;
}
tum check kr rhe ho dp [ ] [ ] != 0 , recursive call nhi rukega
if(dp[lengthA-a.length()+1][lengthB-b.length()+1]!=0)
return dp[lengthA-a.length()+1][lengthB-b.length()+1];
Here you are filling 0 in some case and you are Checking dp [] [ ] != 0