Skip to content

Instantly share code, notes, and snippets.

@pradeexsu
Created May 12, 2021 09:42
Show Gist options
  • Save pradeexsu/c31e40a6515fa4217e0a9c505dec9310 to your computer and use it in GitHub Desktop.
Save pradeexsu/c31e40a6515fa4217e0a9c505dec9310 to your computer and use it in GitHub Desktop.
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
bool is_valid(string &p, string &s, int i, int j){
if(j==s.size() and i==p.size()){
return true;
}
if(j==s.size() or i==p.size()){
return false;
}
if(p.size()-j>s.size()-i){
return false;
}
if(s[j]=='?'){
return is_valid(p, s, i+1,j+1);
}
if(s[j]!='*'){
return s[j]==p[i] && is_valid(p, s,i+1,j+1);
}
if(s[j]=='*'){
for (int k=i; k<p.size(); k++){
if(is_valid(p,s,k,j+1)){
return true;
}
continue;
}
}
return true;
}
int main(){
string s,p;
cin>>s>>p;
if(is_valid(p,s,0,0)){
cout<<"True\n";
}
else{
cout<<"False\n";
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment