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

Try It

 

Translate »