Microsoft Interview Question
Software Engineer / Developersint regexpr(char *r,char *str)
{
int flag = 1;
while(*r && *str)
{
if(*r != '?' && *r != '*')
{
if(*r == *str)
{
str++;
r++;
continue;
}
else
{
flag = 0;
return 0;
}
}
else if(*r == '?')
{
str++;
r++;
continue;
}
else if(*r == '*')
{
while(*r == '*' || *r == '?')
r++;
while(*str != *r)
str++;
continue;
}
}
if(*str != '\0' && *r != '\0')
return 0;
else
return 1;
}
<pre lang="java" line="1" title="CodeMonkey30014" class="run-this">public static boolean is_match(String input, String pattern){
if(pattern=="*") return true;
int inputIndex=0;
int patternIndex = 0;
for(; inputIndex<input.length(); inputIndex++){
if(patternIndex==pattern.length()) break;
if(pattern.charAt(patternIndex)=='*'){
char nonStarChar = ' ';
while(++patternIndex<pattern.length()){
if(pattern.charAt(patternIndex)!='*'){
nonStarChar = pattern.charAt(patternIndex);
break;
}
}
if(nonStarChar==' ') return true;
while(inputIndex<input.length()){
if(input.charAt(inputIndex)==nonStarChar){
inputIndex--;
break;
}
inputIndex++;
}
if(inputIndex==input.length()) return false;
else continue;
}
else if(input.charAt(inputIndex)==pattern.charAt(patternIndex)){
patternIndex++;
continue;
}
else break;
}
if(inputIndex==input.length() && patternIndex==pattern.length()) return true;
return false;
}</pre><pre title="CodeMonkey30014" input="yes">
</pre>
i'm just trying to capture some very raw idea coming on the top of my head:
it likes a dynamic programming.hasToMatch() means from s.at(sStart) on, it has to fully match on partern from pStart
isMatch(string s, string partern,int sStart, int pStart)
{
if(sStart<0) return false;
if(partern.length==pStart)
return true;
if(partern.at(pStart) == "*")
return isMarth(s,partern, sStart, pStart+1)
else
{
int i=hasToMatch(s,partern, sStart,pStart);
return (isMatch(s,partern, sStart+i,pStart+i) || isMatch(s,partern,sStart+1,pStart))
}
}
int hasToMatch(string s, string partern, int sStart, int pStart)
{
int i=0;
while (partern.at(pStart+i)!="*")
{
if(partern.at(pStart+i) == s.at(sStart+1))
i++;
else return -sStart;
}
return i;
}
Do a recursion every time you encounter a '*'.
public static bool SearchWildCard(string text, string pattern, int textPosition, int patternPosition)
{
int i = 0;
while (textPosition + i < text.Length && patternPosition + i < pattern.Length)
{
if (pattern[patternPosition + i] == '*')
{
if (SearchWildCard(text, pattern, textPosition+i, patternPosition+i + 1))
return true;
else
{
textPosition++;
i = 0;
}
}
else
{
if (text[textPosition + i] == pattern[patternPosition + i] || pattern[patternPosition + i] == '?')
i++;
else
{
textPosition++;
i = 0;
}
}
}
if (patternPosition + i == pattern.Length)
return true;
else
return false;
}
}
It's sadly to say that the recursion method fails on the following tests:
(The last parameter is what value should method return.)
TestIsMatch("", "*", true); //
TestIsMatch("", "**", true); //
TestIsMatch(" ", " *", true);//
TestIsMatch("a", "", false);//
TestIsMatch("asdasdasdabc abc", "abc*abc", false);//
TestIsMatch("asdasdasdabc abc", " *abc", false);//
TestIsMatch("asdasdasdabc abcasd", "abc*abc", false);//
Just tested this for several inputs like H*l*o, H*, H*l*l*, H*l*l*o and they all seem to work:
/// <summary>
/// Removes the char.
/// </summary>
/// <param name="str">The STR.</param>
/// <param name="i">The i.</param>
/// <returns></returns>
private string RemoveChar(string str, int i)
{
if (str == null)
{
return null;
}
if (str.Length == 0)
{
return string.Empty;
}
StringBuilder builder = new StringBuilder(str.Length - 1);
for (int j = 0; j < str.Length; j++)
{
if (i != j)
{
builder.Append(str[j]);
}
}
return builder.ToString();
}
/// <summary>
/// Matches the pattern
/// </summary>
/// <param name="text">The text.</param>
/// <param name="pattern">The pattern.</param>
/// <returns>True if pattern is matched, False otherwise</returns>
private bool PatternMatch(string text, string pattern)
{
if ((text == null) || (pattern == null))
{
return false;
}
if (text.Length == 0)
{
return ((pattern.Length == 0) || ((pattern.Length == 1) && (pattern[0] == '*')));
}
// Since we checked for text.Length to be 0 above
// If we hit pattern.Length 0 then pattern does not match
if (pattern.Length == 0)
{
return false;
}
string newPattern = RemoveChar(pattern, 0);
if (pattern[0] != '*')
{
return (text[0] == pattern[0]) && (PatternMatch(RemoveChar(text, 0), newPattern));
}
// No characters matched with *
if (PatternMatch(text, newPattern))
{
return true;
}
for (int i = 0; i < text.Length; i++)
{
string nonStarredString = text.Substring(i + 1);
if (PatternMatch(nonStarredString, newPattern))
{
return true;
}
}
return false;
}
/// <summary>
/// Pattern can contain any characters + '*' character which means zero or more characters.
/// For example: is_match("hello", "h*o") returns true; is_match("hello", "hel*lo") also returns true.
/// </summary>
[TestMethod]
public void PatternMatch()
{
string text = "Hello";
string pattern = "H*l*l*o";
Assert.IsTrue(PatternMatch(text, pattern));
}
bool Tokenizer::searchPattern(char *str, char *pat) {
int i=0, j=0;
int firstToken = parseToken(str,pat,&i,&j,'*'); // Get the first token and try to match the pattern
if(firstToken==-1) return false; // If no such first pattern, return false
if(pat[j]==NULL) return true; // If we reached end of the pattern, return true
int secondToken = parseToken(str,pat,&i,&j,NULL); // Get the second token after the '*'
if(secondToken==-1) return false; // If no such second pattern, return false
return true; // Yay! Found it.
}
int Tokenizer::parseToken(char *str, char *pat, int *i, int *j, char stopChar) {
int k = *j;
while(str[*i]!=NULL && pat[k]!=NULL)
{
if(str[(*i)++]==pat[k])
k++;
else
k=*j;
if(pat[k]==stopChar)
{
*j = k + 1;
return *i;
}
}
return -1;
}
bool isMatch(char *text,char *pattern){
if (text == NULL || pattern == NULL)
return false;
if (*pattern == '\0')
return *text == '\0';
if (*pattern != '*')
return (*pattern==*text) && isMatch(text+1,pattern+1);
else{
return (isMatch(text,pattern+1)) ||
((*text != '\0') && isMatch(text+1,pattern));
}
}
#include <iostream>
//You can write validate pattern function.
bool compareWithPattern(const char* input, const char* pattern)
{
while(*pattern != '\0')
{
if(*pattern == '*')
{
pattern++;
while(*pattern != *input)
{
if (*input == '\0')
{
return false;
}
else
{
input++;
}
}
}
if(*pattern != *input)
return false;
++pattern;
++input;
}
return true;
}
bool findPattern(const char* input, const char* pattern)
{
bool found = false;
while(*input != '\0')
{
if (*input == *pattern)
{
found = compareWithPattern(input,pattern);
input++;
if(found)
break;
}
else
{
input++;
}
}
return found;
}
int main()
{
char* input = "I am great, nil is ueless";
char* pattern = "s*s";
bool result = findPattern(input, pattern);
std::cout<<result;
}
<pre lang="" line="1" title="CodeMonkey14249" class="run-this">void PatternMatching(char*& word, char*& pattern)
{
int i = 0;
int j;
int len_word = strlen(word);
int len_pattern = strlen(pattern);
int num_words;
while(pattern[i] != '*')
{
if(word[i] == pattern[i])
{
i++;
}
else
{
break;
}
}
num_words = len_pattern - i - 1;
for(j = 0; j< num_words; j++)
{
if(pattern[len_pattern - 1] == word[len_word - 1])
{
len_pattern--;
len_word--;
}
else
{
break;
}
}
if(i + j + 1 == strlen(pattern))
{
printf("Pattern matched \n");
}
else
{
printf("unmatched pattern \n");
}
}
</pre><pre title="CodeMonkey14249" input="yes">
</pre>
class Program
{
static void Main(string[] args)
{
string text = "Hello";
string patten = "Hello";
Console.WriteLine(text + ":" + patten + isMatch(text,patten));
patten = "H*";
Console.WriteLine(text + ":" + patten + isMatch(text, patten));
patten = "M*";
Console.WriteLine(text + ":" + patten + isMatch(text, patten));
patten = "*o";
Console.WriteLine(text + ":" + patten + isMatch(text, patten));
text = "hell";
Console.WriteLine(text + ":" + patten + isMatch(text, patten));
patten = "H*o";
text = "Hello";
Console.WriteLine(text + ":" + patten + isMatch(text, patten));
patten = "H?*o";
text = "Hello";
Console.WriteLine(text + ":" + patten + isMatch(text, patten));
patten = "H?*lo";
text = "Helko";
Console.WriteLine(text + ":" + patten + isMatch(text, patten));
Console.Read();
}
static bool isMatch(string text, string pattern)
{
if (pattern.Length == 0) return false;
if (text.Length == 0) return false;
// pattren has "*","?"
int textStartIndex = 0;
int textEndIndex = text.Length - 1;
int PatternStartIndex = 0;
int PatternEndIndex = pattern.Length - 1;
while (PatternStartIndex < PatternEndIndex)
{
switch (pattern[PatternStartIndex])
{
case '*':
while(PatternEndIndex > PatternStartIndex )
{
if (pattern[PatternEndIndex] != text[textEndIndex])
{
return false;
}
PatternEndIndex --; textEndIndex --;
}
break;
case '?':
PatternStartIndex ++;
textStartIndex ++;
break;
default:
if (pattern[PatternStartIndex] != text[textStartIndex])
{
return false;
}
PatternStartIndex++; textStartIndex ++;
break;
}
}
return true;
}
#include<iostream>
using namespace std;
bool isMatch(const char *s,const char *p);
int main()
{
char *s="hello";
char *p="";
if(isMatch(s,p))
cout<<"match";
else
cout<<"no match";
}
bool isMatch(const char *s, const char *p) {
if(*p == '\0')
return (*s == '\0');
if(*p!='*')
return (*p==*s && isMatch(s+1,p+1));
while(*s!='\0')
{
if(isMatch(s,p+1))
return true;
s++;
}
return isMatch(s,p+1);
}
#include<iostream>
using namespace std;
bool isMatch(const char *s,const char *p);
int main()
{
char *s="hello";
char *p="hel*o";
if(isMatch(s,p))
cout<<"match";
else
cout<<"no match";
}
bool isMatch(const char *s, const char *p) {
if(*p == '\0')
return (*s == '\0');
if(*p!='*')
return (*p==*s && isMatch(s+1,p+1));
while(*s!='\0')
{
if(isMatch(s,p+1))
return true;
s++;
}
return isMatch(s,p+1);
}
IMHO - Most people will not have time to go through code. A neatly explained algorithm works the best.
As for this question. This is my suggestion
1) Divide the pattern into 2 parts so that first part doesn't have a '*'. e.g. Divide "ab*bc*cd" into "ab" and "bc*cd"
2) Using KMP find first occurrence of "ab". For the rest of string, recursively search for the pattern "bc*cd". If match is found return true.
3) Repeat for remaining occurrence of "ab".
4) Return false if not more instance of "ab" lest.
<pre lang="c++" line="1" title="CodeMonkey23602" class="run-this">bool is_match(const char * text, const char * pattern)
- Anonymous December 25, 2010{
const char equal_char = '@';
size_t text_len = strlen(text);
if(!text_len)
throw std::invalid_argument("wrong text`s length");
size_t patt_len = strlen(pattern);
if(!patt_len)
throw std::invalid_argument("wrong pattern`s length");
if(strchr(pattern, '*') == NULL)
throw std::invalid_argument("pattern has no \"*\"");
char * compare_str;
if(text_len >= patt_len)
{
compare_str = new char[text_len];
if(pattern[0] == '*') {
int i = text_len - 1, j = patt_len - 1;
while(pattern[j] != '*')
compare_str[i--] = pattern[j--];
memset(compare_str, equal_char, i + 1);
}
else if (pattern[patt_len - 1] == '*') {
int i = 0;
while(pattern[i] != '*')
compare_str[i] = pattern[i++];
memset(compare_str + i, equal_char, text_len - i);
}
else {
int i = 0;
while(pattern[i] != '*')
compare_str[i] = pattern[i++];
int j = text_len - 1;
int k = patt_len - 1;
while(pattern[k] != '*')
compare_str[j--] = pattern[k--];
memset(compare_str + i, equal_char, j - i + 1);
}
}
else
{
int i = 0, j = 0;
compare_str = new char[patt_len];
while(pattern[i])
{
if(pattern[i] != '*')
compare_str[j++] = pattern[i];
++i;
}
}
for(int i = 0; i < text_len; ++i)
{
if(text[i] == compare_str[i] || compare_str[i] == equal_char)
continue;
delete[] compare_str;
return false;
}
delete[] compare_str;
return true;
}</pre><pre title="CodeMonkey23602" input="yes">
</pre>