Home » Technical Interview Questions » String Interview Questions » wildcard character matching

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

READ  Letter Case Permutation

 

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions
Core Java Interview Questions

AD Blocker Detected !

Advertisements help running this website for free.

To view the content please disable AdBlocker and refresh the page.

Wait !!!

You can Crack Technical Interviews of Companies like Amazon, Google, LinkedIn, Facebook, PayPal, Flipkart, etc

Abhishek

Abhishek was able to crack Microsoft after practicing questions from TutorialCup