Microsoft Interview Question
Country: India
this will not work when we have multiple pattern substr in test string, for example :
test string is : "abcdeabchiabc"
pattern : *abc
Now according to your approach this will return no, but it should return true
and this is not a O(n) algo, it's complexity is O(n*strlen(max size sub-string in pattern)), which can be O(n*m) also in worst cases,
@sonesh To your 1st point..yes it will work..First the algo gets the pattern abc, then finds it right in the beginning of the main string.
To your 2nd point: what I mean was for each patter it is O(n)..of course it depends how many substrings need to be matched
int isMatching(char *s,char *p)
{
int si=0,pi=0,sl,pl;
sl=strlen(s);
pl=strlen(p);
int star=-2;
while(si<sl&&pi<pl)
{
if(p[pi]=='*')
star=pi++;
else if(p[pi]==s[si])
pi++,si++;
else
{
pi=star+1;
if(p[pi]==s[si]) // if(p[pi]!=s[si]) this will also work, but will take an extra condition check when this 'if' is false
pi++,si++; // si++;
else
si++;
}
}
if(pi==pl)
if(p[pi-1]=='*' || si==sl)
return 1;
else
return 0;
else
if(p[pi]=='*' && pi+1==pl)
return 1;
else
return 0;
}
This can probably be optimized, here is my first attempt:
bool isMatching (const string &str, const string &pattern)
{
vector <string> search;
size_t cur_pos = 0;
size_t prev_pos = -1;
while ((cur_pos = pattern.find ("*", cur_pos)) != string::npos)
{
if (prev_pos != -1 && prev_pos != cur_pos)
{
search.push_back (pattern.substr (prev_pos, cur_pos - prev_pos));
}
prev_pos = ++cur_pos;
}
cur_pos = 0;
for (const auto &x : search)
{
cur_pos = str.find (x, cur_pos);
if (cur_pos == string::npos)
return false;
cur_pos++;
}
return true;
}
Note: Code written in C++11.
// codes-to-problem.blogspot.in/2012/11/write-function-to-check-given-string.html
public class isMatchingWithWildcard {
public static void main(String [] args){
String pattern = "*abc*def*.doc*";
String str = "adsfabcxyzdefgh.do1docx";
if(isMatching(str, pattern))
System.out.print("Matching");
else
System.out.print("Not Matching");
}
public static Boolean isMatching(String str, String pattern){
int l = pattern.length();
if(pattern.lastIndexOf("*") == l-1)
pattern= (String) pattern.subSequence(0, l-1);
if(pattern.charAt(0) == '*')
pattern= (String) pattern.subSequence(1, pattern.length());
pattern = pattern.replace("*", "__");
String [] patternArray = pattern.split("__");
String sorttenString =str;
for(String aPattern:patternArray){
String [] temp = sorttenString.split(aPattern);
if(temp.length==1 && (aPattern == patternArray[patternArray.length-1]
&& !sorttenString.toLowerCase().contains(aPattern.toLowerCase())))
return false;
str.substring(temp[0].length()+aPattern.length());
}
return true;
}
}
Here is my solution. It is recursive-based. I believe this approach is more easy to understand. (* this is written in c#)
public class WildcardMatcher
{
public static bool isMatching(String str, String pattern)
{
if (0 == pattern.Length) {
// basis case: when pattern is empty.
// in this caes, only empty string is matched.
return 0 == str.Length ? true : false;
} else if (1 == pattern.Length) {
// basis case: when pattern has only one character.
// if it is '*', then all strings are matched.
// if it is not '*', compare with str.
if (pattern.Equals("*")) {
return true;
} else {
return pattern.Equals(str);
}
} else {
// recurssive case: pattern has more than 2 characters.
char pattern_first_char = pattern[0];
if ('*' == pattern_first_char) {
// if the first character of pattern is '*'
// find the first character in the pattern that is not '*'.
// then, try matching with the substring of given string
// that starts with the character.
int i = 0;
do {
++i;
} while ('*' == pattern[i]);
char pattern_next_char = pattern[i];
String pattern_rest = pattern.Substring(i);
for (int j = 0; j < str.Length; ++j) {
if (pattern_next_char == str[j] && isMatching(str.Substring(j), pattern_rest)) {
return true;
}
}
return false;
} else {
// if the first character of pattern is not '*',
// compare the first character of string & pattern.
// if it matches, continue matching for rest part of string & pattern.
char str_first_char = str[0];
if (pattern_first_char == str_first_char) {
String str_rest = str.Substring(1);
String pattern_rest = pattern.Substring(1);
return isMatching(str_rest, pattern_rest);
} else {
return false;
}
}
}
}
}
if you are willing to use the API (methods) in the String class provided by C# then why not just use the Contains() method that support wild card search (which will make the solution even more ridiculous than yours) or why not split the pattern string with ' * ' character iterate througjh the splitted string array find the index of the current iterator value in the given string then search for the next iterator value in the substring from index of current iterator + iteratorValue.Length till the string end. This will as much ridiculous as your solution but much more neater code.
Simplest way is to use split. Runtime: O(m+n)
public static boolean isMatch( String pattern, String str )
{
if( pattern == null || str == null )
return false;
String[] subpatterns = pattern.split("\\*");
int pos = 0;
for( int i = 0; i < subpatterns.length; i++ )
{
if( pos >= str.length() )
return false;
if( subpatterns[i].length() > 0 && pos < str.length() )
{
int index = str.indexOf(subpatterns[i], pos );
if( index == -1 )
return false;
else
pos += subpatterns[i].length();
}
}
return true;
}
public class StarPattern {
public static boolean isMatch(String string, String pattern) {
boolean isMatch = true;
String[] patterns = pattern.split("\\*");
int index = 0;
int i;
for (i = 0; i < patterns.length; i++) {
if (string.substring(index).indexOf(patterns[i]) == -1) {
isMatch = false;
return isMatch;
}
index += string.substring(index).indexOf(patterns[i])
+ patterns[i].length();
}
if (i != patterns.length) {
isMatch = false;
}
// corner case detection
if (pattern.charAt(0) != '*') {
isMatch = string.startsWith(patterns[i-1]);
}
if (pattern.charAt(pattern.length() - 1) != '*') {
isMatch = string.endsWith(patterns[i-1]);
}
return isMatch;
}
public static void main(String[] args) {
String string = "adsfabcxyzdefgh.docx";
// String string = "adsfabcxyzdefgh.do.docxyz";
String pattern = "*abc*def*.doc*";
// String string = "abcdeabchiabc";
// String pattern = "*abc";
System.out.println(isMatch(string, pattern));
}
}
This is O(n) solution
- artemis November 25, 2012