Wrong test case

#1

Ome test case is failing in my code.
Please help me.

#2

#include <bits/stdc++.h> using namespace std; #define MOD 1000000007 int dp[100005][405]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); long t; t=1; while(t–){ string a,b; cin>>a>>b; long n=a.size(),m=b.size(); // char ch; memset(dp,0,sizeof(dp)); dp[0][0]=1; for(long i=1;i<=m;i++) if(b[i-1]==’’) dp[0][i]=dp[0][i-2]; for(long i=1;i<=n;i++){ for(long j=1;j<=m;j++){ if(a[i-1]==b[j-1] || b[j-1]==’.’ ) dp[i][j]=dp[i-1][j-1]; else if(b[j-1]==’’ ){ if (b[j-2]!=a[i-1]&& b[j-2]!=’.’) dp[i][j]=0; else dp[i][j]= dp[i][j-1] || dp[i-1][j]; } // cout<<dp[i][j]<<" "; } // cout<<endl; } cout<<dp[n][m]<<endl; } }

#3

hello @mkg825412gir

pls save ur code here-> https://ide.codingblocks.com/

and share its link with me

#4
#5

the dp size is not correct.
we dont know what can be row and column beforehand so dont inititalise dp array of fixed row and column.

secondly look at the constraint. it is not possible to solve it in quadratic space, try to do some space optimisation.
like->
a) a*****bbb then u can remove all extra consecutive * -> a*b
this way the dp will take less space.

b)or u can try to solve it in linear space

#6

solution in linear space complexity->

#7

Thanks. I got it. Size problem.

#8

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.