Flipkart Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
haha, I choose Perl to implement this:
$exp = q(^ab..*abc$);
$test = q(abyxxxxabc);
print "$exp, $test, " . evaluate($exp, $test)."\n";
sub evaluate{
my $Exp = shift;
my $testCase = shift;
return "false" if ($testCase !~ /^[a-z]+[a-z]$/); # contain only character in [a-z]?
if ($testCase =~ $Exp){
return "true";
}
else{
return "false";
}
};
^ and $ can be neglected removed as string without same also mean the same thing. Here is a dyanamic approach to the problem
bool isMatch(const char *s, const char *p) {
int n=strlen(s), m=strlen(p), i, j, chars=0;
//check if pattern have less that equal to character then string
for(i=0; p[i]!='\0'; ++i) if(p[i]!='*' && n<++chars) return false;
vector<bool> dp(n+2,false);
// dp[n] is true fo first time,
// i.e end of string charater is true to enable correct match for last pattern character
// At any time dp[i] == 1 mean we have match from i to n index
for(i=m-1, dp[n]=true; i>=0; --i){
if(p[i]=='*'){
while(i>0 && p[i]==p[i-1]) --i; //skip multiple *
for(j=n; j>=0 && !dp[j]; --j);
for(; j>=0; --j) dp[j]=true;
}else{
for(j=0; j<n+1; ++j)
dp[j]=(p[i]==s[j] || p[i]=='?') ? dp[j+1] : false;
}
}
return dp[0];
}
This is from a programming contest/website.
- Anonymous March 19, 2014