Microsoft Interview Question
Software Engineer / DevelopersTeam: STC
Country: China
Interview Type: Phone Interview
#/usr/bin/python
def match(string, pattern):
if len(pattern) == 0 and len(string) == 0:
return True
if (len(pattern) == 0 and len(string) > 0) or (len(pattern) > 0 and len(string) == 0):
return False
if pattern[0] == "*":
return match(string[1:], pattern[1:]) or match(string[1:], pattern)
elif pattern[0] == string[0]:
return match(string[1:], pattern[1:])
else:
return False
print match("abracadabra", "ab*ca*br*")
bool isMatchGeneral(const char *s, const char *p, int slen, int plen)
{
if (s == NULL && p == NULL) return true;
if (s == NULL || p == NULL) return false;
if (plen == 0) return true;
if (*p == '*') return isMatchGeneral(s, p+1, 0, plen-1);
if (slen == 0) return false;
int i=0;
while (i < slen)
{
int j=0;
while (s[i] != p[j])
{
i++;
if (i == slen) return false;
}
int reserve = i;
while (s[++i] == p[++j])
{
if (j==plen) return true;
if (i==slen) return false;
}
if (j == plen) return true;
if (p[j] == '*') return isMatchGeneral(s+i, p+j+1, slen-i, plen-j-1);
if (i == slen) return false;
i = reserve + 1;
}
return false;
}
bool isMatch(const char *s, const char *p, int slen, int plen) {
if (s == NULL && p == NULL) return true;
if (s == NULL || p == NULL) return false;
if (slen == 0 && plen == 0) return true;
if (slen == 0)
{
if (*p == '*') return isMatch(s, p+1, 0, plen-1);
else return false;
}
if (*p != '*')
{
if (*s != *p) return false;
else return isMatch(s+1, p+1, slen-1, plen-1);
}
if (p[plen-1] != '*')
{
if (s[slen-1] != p[plen-1]) return false;
else return isMatch(s, p, slen-1, plen-1);
}
return isMatchGeneral(s, p+1, slen, plen-2);
}
int _tmain(int argc, _TCHAR* argv[])
{
char * s = "aaaabaaaaac";
char * p = "a*ab*ba**c";
cout<<isMatch(s, p, strlen(s), strlen(p))<<endl;
char j;
cin>>j;
return 0;
}
int match(const char *pattern, const char *string)
{
register char c;
while(1){
switch(c = *pattern++)
{
case '*':
c = *pattern;
while(*string){
if(1 == match(pattern, string))
return 1;
++string;
}
break;
case '\0':
return !*string ? 1 : 0;
break;
default:
if(c != *string++)
return 0;
break;
}
}
}
int match(const char *pattern, const char *string)
{
register char c;
while(1){
switch(c = *pattern++)
{
case '*':
c = *pattern;
while(*string){
if(1 == match(pattern, string))
return 1;
++string;
}
break;
case '\0':
return !*string ? 1 : 0;
break;
default:
if(c != *string++)
return 0;
break;
}
}
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;
bool checkForMatch(const char* str, const char* pattern){
if(str == NULL && pattern == NULL){
printf("both pattern and string are null\n");
return true;
}
if(str == NULL && pattern != NULL){
printf("Pattern is not null but string is null\n");
return false;
}
if (*pattern == '*'){
printf("Pattern is starting with *\n");
return false;
}
if (pattern == NULL && str != NULL){
printf("Pattern is null but string is not null\n");
return false;
}
char* patternStart = (char*) pattern;
char* patternBegin = (char*) pattern;
int index = 0;
int count = 0, i=0;
char* subStr = NULL;
int origLen = strlen(str);
while(*patternStart){
count = 0;
i = 0;
while(*patternStart && *patternStart != '*'){
count++;
patternStart++;
}
subStr = (char*) malloc(sizeof(char) * (count + 1));
strncpy(subStr, patternBegin, count);
subStr[count] = '\0';
for(; i<count - 1; i++){
if(str[index] != subStr[i]){
return false;
}
index++;
}
while(str[index] == subStr[i]){
index++;
}
patternBegin = ++patternStart;
}
if(index < origLen){
return false;
}
return true;
}
int main(){
char* origStr = "aaabba";
char* regEx = "aa*bb*a";
bool isValid = false;
isValid = checkForMatch(origStr, regEx);
if(isValid){
printf("String matched the expression\n");
}
else{
printf("String didn't matched the expression\n");
}
system("pause");
return 0;
}
Now i have fixed it and here is the correct solution.
=====================================
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;
bool checkForMatch(const char* str, const char* pattern){
if(str == NULL && pattern == NULL){
printf("both pattern and string are null\n");
return true;
}
if(str == NULL && pattern != NULL){
printf("Pattern is not null but string is null\n");
return false;
}
if (*pattern == '*'){
printf("Pattern is starting with *\n");
return false;
}
if (pattern == NULL && str != NULL){
printf("Pattern is null but string is not null\n");
return false;
}
char* patternStart = (char*) pattern;
char* patternBegin = (char*) pattern;
int index = 0;
int count = 0, i=0;
char* subStr = NULL;
int origLen = strlen(str);
while(*patternStart){
count = 0;
i = 0;
while(*patternStart && *patternStart != '*'){
count++;
patternStart++;
}
subStr = (char*) malloc(sizeof(char) * (count + 1));
strncpy(subStr, patternBegin, count);
subStr[count] = '\0';
for(; i<count - 1; i++){
if(str[index] != subStr[i]){
return false;
}
index++;
}
while(str[index] == subStr[i]){
index++;
}
if(*(patternStart + 1) == subStr[i]){
++patternStart;
}
patternBegin = ++patternStart;
}
if(index < origLen){
return false;
}
return true;
}
int main(){
char* origStr = "aaa";
char* regEx = "a*a";
bool isValid = false;
isValid = checkForMatch(origStr, regEx);
if(isValid){
printf("String matched the expression\n");
}
else{
printf("String didn't matched the expression\n");
}
system("pause");
return 0;
}
void reg_expression()
{
string reg_exp;
string test_str;
cout<<"\nEnter the regular expression : ";
cin>>reg_exp;
bool *bFlag;
int nSize = reg_exp.length();
bFlag = new bool[nSize]();
cout<<"Enter the string u want 2 check: ";
cin>>test_str;
int i = 0;
int j = 0;
while(j != test_str.length())
{
if(reg_exp[i] == '*')
{
i++;
continue;
}
if(reg_exp[i] == test_str[j])
{
bFlag[i] = true;
j++;
}
else if(bFlag[i])
{
i++;
}
else
{
break;
}
}
cout<<"\nResult : ";
if((j == test_str.length()) && (i == reg_exp.length() - 1))
{
cout<<" \""<<reg_exp<<"\" can generate string \""<<test_str<<"\".";
}
else
{
cout<<" \""<<reg_exp<<"\" cannot generate string \""<<test_str<<"\".";
}
}}
isMatching(char* pattern, char* string) {
char cur_match = *pattern;
char next = *(pattern+1);
if( next == '*') { //Multiple character matching a*
while( *string == cur_match)
string++;
pattern+=2;
}
else{ //Single Character match (Eg aa* here match only the first a)
if(*string != cur_match)
return false;
string++;
pattern++;
}
}
C# code for taking care of * and ?
public static bool PatternMatch(string text, string pattern)
{
// Validate input
// can text contain regex characters??
// this code doesn't take care or escaping regex character
return PatternMatch(text, 0, pattern, 0);
}
private static bool PatternMatch(string text, int txtInd, string pattern, int patInd)
{
if (text.Length == txtInd && pattern.Length == patInd)
return true;
if (text.Length == txtInd || pattern.Length == patInd)
return false;
if ((text[txtInd] == pattern[patInd]) || (pattern[patInd] == '?'))
return PatternMatch(text, txtInd+1, pattern, patInd+1);
if (pattern[patInd] == '*')
return PatternMatch(text, txtInd+1, pattern, patInd+1) || PatternMatch(text, txtInd, pattern, patInd+1) || PatternMatch(text, txtInd+1, pattern, patInd) ;
else return false;
}
#include<stdio.h>
#include<string.h>
int stringMatch(char * pattern , char * str ){
int pointer=0;
char c;
int count;
while ( pattern[0] != '\0' ){
c=pattern[0];
if ( pattern[1] == '*' ){
count=-1;
pattern+=2;
} else {
count=1;
pattern+=1;
}
switch ( count ){
case 1:
if ( str[pointer] == c )
pointer++;
else
return 0;
break;
case -1:
while ( str[pointer] == c )
pointer++;
}
}
if ( pointer == strlen(str) )
return 1;
else
return 0;
}
is it not very similar to string compression ,, traverse the string... replace all similar symbols by symbol* .. do till end of string .. then compare with the given expression ... eg given string aaaaaaaabbbbbbbcccccc .. given expression a*b*c* .. traverse string till you reach b... replace all a's by a* same for b and then c.. compare with a*b*c* .. it matches .. hence true,,
Here is a generalization of this problem:
- Andy April 09, 2012basicalgos.blogspot.com/2012/03/10-regular-expression-matching.html