➤ Problem Link : AUTOMATA
👉 Hint : Simple 2D DP
✅ C++ Solution :
#include<bits/stdc++.h> using namespace std; bool dp[1000][1000]; int main() { int t; cin>>t; string l,s; while(t--) { memset(dp,0,sizeof(dp)); cin>>l; cin>>s; l.insert(0,"0"); s.insert(0,"0"); int s1=l.size(); int s2=s.size(); dp[0][0]=1; for(int i=1;i<s1;i++) { for(int j=1;j<s2;j++) { if(l[i]==s[j]) dp[i][j]=dp[i-1][j-1]; else if(l[i]=='?') dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]); else if(l[i]=='*') { for(int k=j;k>=1;k--) dp[i][j]=max(dp[i][j],dp[i-1][k]); } } } if(dp[s1-1][s2-1]) cout<<"Yes"<<endl; else cout<<"No"<<endl; } }
Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook.
😇Happy Learning!!