Check if two strings match where one string contains wildcard characters

Program to check if two strings match where one string contains wildcard characters is discussed here.

DESCRIPTION:

Given a text and pattern string. The pattern consists of the following characters

‘+’: It can be replaced with 0 or more occurrence of the previous character
‘*’: Matches any sequence of characters (including the empty sequence)
‘?’: It can be replaced with a single occurrence of any character.

The task is to determine if the string and pattern match after successfully replacing the special characters in the pattern with the above rules. Print “true” if the text and pattern match else print “false”

Test Cases: The first string is the pattern and the second string represents the text

Sample Input 1:
String 1: Am?zo
String 2: Amazon

Sample Output :
FALSE

Sample Input 2:
String 1: Am?z*on
String 2: Amazkfdsaon

Sample Output 2:
TRUE

Algorithm to check if two strings match where one string contains wildcard characters

  • Input two strings where string 1 contains wildcard characters.
  • Check both the strings character by character.
  • If a character of string 1 contains a ‘*’ or ‘+’, take the next character from string 1 and check for that character in string 2. If found, continue checking the next character, else return false.
  • If the character of string 1 contains a ‘?’, check if the immediate next character of string 1 and the next character of string 2 match. If they match, proceed checking with the next character. Else, return false.
  • Continue the same process until all the characters have been traversed.

Program to check if the two strings match where one string contains wildcard characters is given below.

/* C++ program to check if the two strings are same where one strings contains wildcard characters */

#include <iostream>
using namespace std;

int main() {
string pattern,checkS;
cin>>pattern;
cin>>checkS;
bool TRUE=true,FALSE=false;
bool dp[pattern.length()+1][checkS.length()+1];
dp[0][0]=TRUE;
for(int i=1;i<=checkS.length();i++)
   dp[0][i]=FALSE;
for(int i=1;i<=pattern.length();i++)
   if(pattern[i-1] == ‘*’)
       dp[i][0]=dp[i-1][0];
   else
       dp[i][0]=FALSE;
   for(int i=1;i<=pattern.length();i++)
   {
       for(int j=1;j<=checkS.length();j++)
       {
           if(pattern[i-1] == checkS[j-1])
               dp[i][j]=dp[i-1][j-1];
           else if(pattern[i-1] == ‘?’)
               dp[i][j]=dp[i-1][j-1];
           else if(pattern[i-1] == ‘*’)
               dp[i][j]=dp[i-1][j]||dp[i][j-1];
           else if(pattern[i-1] == ‘+’)
                {
                    if(pattern[i-2] == checkS[j-1])
                    {
                        dp[i][j]=dp[i-1][j] or dp[i][j-1];
                    }
                    else
                    {
                        dp[i][j] =FALSE;
                    }
                }
           else
           {
               dp[i][j] =FALSE;
           }
       }
   }
   // for(int i=1;i<=pattern.length();i++)
   // {
   //   for(int j=1;j<=checkS.length();j++)
   //   {
   //       cout<<dp[i][j]<<” “;
   //   }
   //   cout<<endl;
   // }
   if(dp[pattern.length()][checkS.length()])
       cout<<“TRUE”;
   else
       cout<<“FALSE”;
}

Test Case 1

I/P
F*CE
FACE
O/P
TRUE

TestCase 2

I/P
F*SA+C*YFORCAR+E*E+M*T
FOCUSACADEMYFORCARRERENHANCEMENT
O/P
TRUE

Test Case 3

I/P
No+No+
NoooooooooooNooooaoooooo
O/P
FALSE

TestCase 4

I/p
*
Face
O/P
TRUE

TestCase 5

I/p
Am?azon
Amazon
O/p
FALSE