Given two strings s1 and s2, where s1 contains wild card characters and s2 is a normal string. Write a function that will return true if both the given strings match
The following wildcard characters are allowed
‘*’ = Matches with zero or more instances of any character or set of characters
Example :
“Pro*ing” will be matched with “Programming”
‘?’ = Matched with any one character
Example :
“Pro?ing” will be matched witth “Proking”
Example
INPUT :
s1 = “Pro?gr*”
s2 = “Programming”
OUTPUT:
TRUE
Algorithm
1. If there are characters after s1 and no characters after ‘*’ in s2 then return false
2. If the string s1 contains ‘?’ or current characters of both strings match, then do a recursive call to the remaining part of s1 and s2 ie, s1+1, s2+1
3. If there is ‘*’, then there are two possibilities
a. we consider current character of s2 ie, charMatching(s1+1, s2)
b. we ignore the current character of s2 ie, charMatching(s1,s2+1)
C++ Program
#include <bits/stdc++.h>
using namespace std;
bool charMatching(char *s1, char * s2)
{
// If we reach at the end of both strings, we are done
if (*s1 == '\0' && *s2 == '\0')
return true;
// Make sure that the characters after '*' are present
// in s2 string.
if (*s1 == '*' && *(s1+1) != '\0' && *s2 == '\0')
return false;
// If the s1 string contains '?', or current characters
// of both strings match
if (*s1 == '?' || *s1 == *s2)
return charMatching(s1+1, s2+1);
// If there is *, then there are two possibilities
// We consider current character of s2 string or We ignore current character of s2 string.
if (*s1 == '*')
return charMatching(s1+1, s2) || charMatching(s1, s2+1);
return false;
}
int main()
{
char s1[] = "Prog*ing";
char s2[] = "Programming";
if(charMatching(s1, s2))
{
cout<<"TRUE"<<endl;
}
else
{
cout<<"FALSE"<<endl;
}
return 0;
}