Yahoo Interview Question
Software Engineer / DevelopersTested it. It doesn't compile (minor errors) and doesn't work. My function below. Main idea - remember last star (*) position and return back to it when characters in current positions not match.
bool match(char *str, int slength, char *pattern, int plength)
{
int starpos=-1;
int currpos=0;
for(int i=0;i<slength;++i)
{
if (pattern[currpos]=='*')
{
starpos=currpos;
if (currpos+1==plength) return true;
currpos++;
if (str[i]!=pattern[currpos] && pattern[currpos]!='?')
{
--currpos;
continue;
}
else
currpos++;
}
else
{
if (str[i]!=pattern[currpos] && pattern[currpos]!='?')
{
if (starpos==-1) return false;
else currpos=starpos;
}
else
currpos++;
}
if (currpos==plength)
return (i==slength-1);
}
return false;
}
#include<stdio.h>
main(){
FILE *fp;
fp = fopen("input.txt","r");
char reg[1000],query[1000];
int lines=0,words=0,characters=0;
fgets(reg,1000,fp);
fgets(query,1000,fp);
int i=0;
int j=0;
while(reg[i]){
if(reg[i]=='*'){
while(query[j] && reg[i]!=query[j])
j++;
else if(reg[i]=='?'){
i++;
j++;
}
else if(reg[i]==query[j]){
i++;
j++;
}
}
if(!reg[i]&& !query[j])
printf("Yes\n");
else
printf("No\n");
getchar();
}
int match_regexp(char s[], char regexp[])
{
for(char* p = s; *p != '\0'; p++)
if(match_from_here(p, regexp))
return 1;
return 0;
}
static int match_from_here(char *s, char *regexp)
{
if(regexp[0] == '\0')
return 1;
if(regexp[1] == '*')
return match_star(regexp[0], s, regexp+2);
if(regexp[1] == '?')
return (s[0] == regexp[0]) ? match_from_here(s+1, regexp+2) : match_from_here(s, regexp+2);
if(s[0] != '\0' && s[0] == regexp[0])
return match_from_here(s+1, regexp+1);
return 0;
}
static int match_star(char c, char *s, char *regexp)
{
do
{
if(match_from_here(s, regexp))
return 1;
}
while(*s != '\0' && *s++ == c);
return 0;
}
bool match( char* str, char* pat)
- Amit Priyadarshi September 24, 2010{
while (*str)
{ if( (*pat != '*') ||(*pat != '?') )
{
if (*pat == *str)
{
pat++; str++;
}
return false;
}
else if (*pat == '?')
{str++; pat++; }
else if (*pat == '*')
{ while (*pat == '*') pat++;
if (!pat) return true;
while(*str) if (match(*pat,*str++)) return true;
return false;
}
else
{
return false;}
}
}
while(pat == '*') pat++;
return (!*pat)
}