Directi Interview Question Software Engineer / Developers
Country: India
Interview Type: In-Person
Call the string with wild card s1, string without wild card is s2
The idea is use branch and bound so that we can quickly define when we can not proceed matching process any futher. Observation to quickly stop matching as going further will not result in a match
- The length of s1 is longer than s2 then, it will not match since wildcard should have at least 0 length
- If we see wild card at the beginning then start checking for matching at the end where both are different from wildcard and immediately stop when mis-match is found
Futher optimization:
- Keep the length of string available all the time since we can update length in 0(1) while the length of a string might take 0(N) to determine.
- Keep the number of wild card available since trivial case when there is only one wild card *, it will be replace by l2 - l1 of '?' which can be equal to anything (we can do better than this by keeping the matching position)
The complexity is a litte bit hard to predict, it take lineartime for the matching test when there is only one wild card, time complexity depend on the number of wild card and length different (it is 0(1) if s1 is longer than s2 :)).
#include <cassert>
bool isEqual(const char* s1, size_t l1, const char* s2, size_t l2) {
for (int i=0, j = 0; i< l1; ++i, ++j) {
if (s1[i] == '*')
j = j + (l2 - l1);
else if (s1[i] != s2[j])
return false;
}
return true;
}
bool MatchingHelper(const char* s1, size_t l1, size_t w, const char* s2, size_t l2) {
if (l1 - w > l2)
return false;
if (w == 1)
return isEqual(s1, l1, s2, l2);
if (s1[0] == '*') {
for (;s1[l1-1] != '*'; --l1, --l2)
if (s1[l1-1] != s2[l2-1])
return false;
int maxw = l2 - l1 + w;
bool match = false;
for (int i=0; i<= maxw; ++i) {
match = MatchingHelper(s1+1, l1 - 1, w - 1, s2 + 1 + i, l2 - i - 1);
if (match)
return true;
}
return false;
} else {
if (s1[0] != s2[0])
return false;
return MatchingHelper(s1+1, l1 - 1, w, s2+1, l2 -1);
}
}
bool isMatch(std::string s1, std::string s2) {
size_t l1 = s1.length();
size_t l2 = s2.length();
size_t w = 0;
for (int i=0; i< l1; ++i)
w += (s1[i] == '*');
return MatchingHelper(&s1[0], l1, w, &s2[0], l2);
}
int main()
{
assert(isMatch("b*ba","bbba"));
assert(isMatch("b**a","bbba"));
assert(isMatch("*bba","bbba"));
assert(isMatch("bb*a","bbba"));
assert(isMatch("bbb*","bbba"));
assert(!isMatch("bb*c","bbba"));
}
Used recursion to implement this concept
#include <stdio.h>
#include <stdlib.h>
int stringWildCard(char *first,char *second)
{
if(*first=='\0'&&*second=='\0')
return 1;
else if(*first=='*'&&*(first+1)!='\0'&&*second=='\0')
return 0;
else if(*first=='*'&&*(first+1)!=*second&&*(first-1)!=*second)
return 0;
else if(*first=='*')
return stringWildCard(first+1,second)||stringWildCard(first,second+1);
else if(*first==*second)
return stringWildCard(first+1,second+1);
else if(*first!=*second&&*(first+1)=='*')
return stringWildCard(first+2,second);
else if(*first=='+'&&*(first-1)==*(second-1))
return stringWildCard(first,second+1)||stringWildCard(first+1,second);
return 0;
}
void test(char *first,char *second)
{
stringWildCard(first,second)?puts("Yes"):puts("No");
}
int main()
{
test("b*ba", "bbba");
}
I can think of a brute-force solution which is O(NM) where N is the length of the text and M is the length of the pattern. I am also assuming from the question that there is only the wildcard character (*) in the pattern.
The idea is to use recursion to check possible patterns, if there is wildcard character and backtrack, if there isn't a match.
bool match_pattern(char *text, char *pattern) {
if (*pattern == 0)
return *text == 0;
if (*text == 0)
return *pattern == 0;
if ('*' == *pattern) return match_pattern(text+1, pattern) || match_pattern(text, pattern+1);
if (*text == *pattern) return match_pattern(text+1, pattern+1);
return false;
}
I think this code should work and it is fairly simple also.
#include<iostream>
#include<conio.h>
#include<string.h>
using namespace std;
int main()
{
char s[20],p[20];
int counter=0;
cout<<"Enter string one";
gets(s);
int lens= strlen(s);
cout<<"\n Enter string two";
gets(p);
int lenp=strlen(p);
if(lens==lenp)
{
int j=0;
for(int i=0;s[i]!='\0';i++,j++)
{
if(p[j]=='*')
{counter++;
continue;
}
else
if(s[i]!=p[j])
break;
else
counter++;
}
}
if(counter==lenp)
cout<<"String can come";
else cout<<"String cant come";
getch();
}
Sorry, I am adding a generalised approach. This approach will help both on exact one string matching or any number of same string matching. If it is exact one string matching, this idea is not efficient. Please ignore this.
Idea:Modified KMP can be used like follows. complexity o(n)
static void Main(string[] args)
{
p = "*ba*a";
t = "abafa";
b = new int[p.Length + 1];
m = p.Length;
n = t.Length;
KmpPreprocess();
KmpSearchRegularExp();
Console.ReadKey();
}
public static void KmpPreprocess()
{
int i = 0, j = -1;
b[i] = j;
while (i < m)
{
while (j >= 0 && p[i] != p[j])
{
j = b[j];
}
i++; j++;
b[i] = j;
}
}
public static bool report(int n)
{
//do what ever here once found a match
return true;
}
public static void KmpSearchRegularExp()
{
int i = 0, j = 0;
while (i < n)
{
if (j < m && j >= 0 && p[j] == '*')
{
j++; i++;
}
while (j >= 0 && j < m && t[i] != p[j] )
{
j = b[j];
}
++i;
j++;
if (j == m)
{
report(i - j);
j = b[j];
}
}
}
This is another solution. Iam sorry, it might not be too clear. And im too sleepy to write the comments.
Its a non-recursive solution.
It basically checks for a wildcard(*) and if found, it takes the substring between this wildcard and the next, and finds it in S. If found, it moves on to the next wildcard, else returns false.
#include <stdio.h>
#include <string.h>
#define bool _Bool
#define true 1
#define false 0
bool canTransform(char* s, char* p)
{
char* sub = malloc(strlen(p) * sizeof(p));
while(*p != '\0')
{
if(*p != '*' && *p++ != *s++)
return false;
else
{
int i=1, j=0;
sub[0] = '\0';
while(*(p+i) != '\0' && *(p+i) != '*')
*(sub + j++) = *(p + i++);
sub[j] = '\0';
if(sub[0] == '\0')
return true;
i = 0, j = 0;
int slen = strlen(s), sublen = strlen(sub);
while(i <= slen - sublen)
{
int ch;
for(j=0; (ch = sub[j]) != '\0' && s[i+j] == sub[j]; j++)
;
if(ch == '\0') //match!!
{
s = s + i + j;
p = p + j + 1;
break;
}
i++;
} //while
if(slen == strlen(s))
return false;
} //else
}
return true;
}
int main()
{
char* s = "user@mymail.com";
char* p = "*@*.*";
printf(canTransform(s,p) ? "Yes" : "No");
return 0;
}
#include <iostream>
#include <string>
using namespace std;
int main()
{
string in1, in2;
int l1, l2, counter=0,i=0,j=0,temp;
cin >> in1;
cin >> in2;
l1 = in1.size();
l2 = in2.size();
if(l1>l2)
{
cout << 0;
return 0;
}
if(in1=="*")
{
cout << 1;
}
else if(l1==l2)
{
for(int i=0;i<l1;i++)
{
if(in1[i]==in2[i])
{
counter++;
}
else if(in1[i]=='*')
{
counter++;
}
else
{
break;
}
}
if(counter==l1)
{
cout << 1;
return 0;
}
}
else
{
while(i<l1 && j<l2)
{
if(in1[i]==in2[j])
{
counter++;
i++;
j++;
}
else if(in1[i]=='*')
{
for(int x=j;x<l2;x++)
{
if(in2[x]==in1[i+1])
{
j=x;
}
}
i++;
counter=counter+j;
}
else
{
break;
}
}
if(counter==l2)
{
cout << 1;
return 0;
}
}
cout << 0;
}
import java.util.*;
public class dfa {
String s1,s2;
dfa(String a,String b)
{
s1=a;
s2=b;
}
boolean test()
{
if(!starins1())
{
if(s1.length()==s2.length())
{
for(int i=0;i<s1.length();i++)
if(s1.charAt(i)!=s2.charAt(i))
return false;
return true;
}
else
return false;
}
else
{
int i,j=s1.length()-1;
for(i=s2.length()-1;i>=0;i--)
{
if(j>=0)
{
if(s1.charAt(j)=='*')
{
j--;
i++;
}
else if(match(j,i))
{
if(j<s1.length()-1 && s1.charAt(j+1)=='*')
{}
else
j--;
}
else if(!match(j,i) && s1.charAt(j+1)=='*')
{
j--;
i++;
}
else if(!match(j,i))
return false;
else
{
}
}
}
if(i<0 && j==0)
return true;
}
return false;
}
boolean match(int a,int b)
{
if(s1.charAt(a)==s2.charAt(b))
{
return true;
}
else
return false;
}
boolean starins1()
{
int i=s1.indexOf("*");
if(i==-1)
return false;
else
return true;
}
public static void main(String[] args) {
Scanner s=new Scanner(System.in);
System.out.println("Expression String");
String s1=s.next();
System.out.println("Normal String");
String s2=s.next();
dfa d=new dfa(s1,s2);
if(d.test())
System.out.println("Correct");
else
System.out.println("Incorrect");
}
}
static boolean MatchWildChar(String Str, String Pat)
{
if(Str.isEmpty())
return (Pat.isEmpty());
if (Pat.isEmpty())
return false;
if(Pat.charAt(0) == '*') {
return (Match(Str.substring(1), Pat) || Match(Str.substring(1),Pat.substring(1)) || Match(Str,Pat.substring(1)));
}
return ((Pat.charAt(0) == Str.charAt(0)) && Match(Str.substring(1), Pat.substring(1)));
}
bool match(char *first, char * second) { // If we reach at the end of both strings, we are done if (*first == '\0' && *second == '\0') return true; // Make sure that the characters after '*' are present in second string. // This function assumes that the first string will not contain two // consecutive '*' if (*first == '*' && *(first+1) != '\0' && *second == '\0') return false; // If the first string contains '?', or current characters of both // strings match if (*first == '?' || *first == *second) return match(first+1, second+1); // If there is *, then there are two possibilities // a) We consider current character of second string // b) We ignore current character of second string. if (*first == '*') return match(first+1, second) || match(first, second+1); return false;}
- arpitbaheti7 October 12, 2013