# wildcard character matching

## 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;
}```