Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What is a Wildcard Match?
3.
Problem Statement
4.
Solution Approach 
4.1.
Case 1: if p[i] == ‘?’
4.2.
Case 2: if p[i] == some alphabet
4.3.
Case 3: if p[i]==’*’ 
5.
Approach 1: Recursion
5.1.
Implementation of the above idea using recursion is as follows
6.
C++
6.1.
Input
6.2.
Output
7.
Time complexity
7.1.
Space complexity
8.
Approach 2: Dynamic Programming
8.1.
Implementation 
8.2.
C++
8.2.1.
Input
8.2.2.
Output
8.3.
Time complexity
8.4.
Space complexity
9.
Frequently asked questions
9.1.
What are the two types of wildcards?
9.2.
What is the difference between match and wildcard?
9.3.
How do you match wildcards?
9.4.
What is the difference between wildcard matching and regular expression matching?
10.
Conclusion
Last Updated: May 22, 2024
Easy

Wildcard Matching

Author Shreya Deep
2 upvotes
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

Matching two strings means that they both should be equal to each other. If we’re given a pattern, it might be containing a few temporary characters denoted by some symbols, which can be replaced with a single or a bunch of alphabet characters. So to match a pattern with a given text, you need to efficiently replace those temporary characters with suitable characters that can lead to the exact given text.

In this blog, we’ll learn how to solve a problem named wildcard matching where we have to determine whether a pattern can be matched to a given text or not.

Wildcard Matching

What is a Wildcard Match?

A wildcard match is a technique used to compare text strings where the pattern may contain special characters representing unknown characters. These special characters, called wildcards, allow you to match a broader range of strings without having to specify every single possibility.

Here are the most common wildcards and their meanings:

  • * (asterisk): Matches any sequence of characters (including zero characters).
    • Example: f*d matches "food", "fund", "fed", and even "fd" (empty sequence).
  • ? (question mark): Matches exactly one character at that position in the string.
    • Example: c?t matches "cat", "cut", or "cit", but not "cart" or "ct".
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Problem Statement

Given a text and a wildcard pattern, determine whether that pattern can be matched with the text or not. The matching should cover the entire text. Return true if the pattern can be equated to the text otherwise, false. 

Note:   

  • The wildcard pattern can include characters ‘?’ and ‘*.’ 
  • ‘?’: matches any single character.
  • ‘*’: matches any sequence of characters (including the empty line)
  • Each occurrence of ‘?’ can be replaced with any character, and each occurrence of ‘*’ can be replaced with a sequence of characters such that the wildcard pattern becomes identical to the input string after replacement.


For example: 

INPUT : Text - “adceb”  Pattern - “*a*b”

OUTPUT:  true

Explanation: the ‘*’ at the 0th position of the pattern can be replaced by an empty sequence, and the ‘*’ at the 2nd position can be replaced by “dce.”

INPUT : Text - “acdcb”  Pattern - “a*c?b”

OUTPUT:  false

Explanation: No perfect replacement can be done. 

Solution Approach 

First, let’s see the different types of characters in the pattern p.

There can be 3 cases:

Case 1: if p[i] == ‘?’

  • Replace the ‘?’ with the current character in the text string and move to the next character in both the text and the pattern.

Case 2: if p[i] == some alphabet

  • See if the alphabet is equal to the current character in the text string. If it is similar, move to the next character in both the text and the pattern. Otherwise, return false.

Case 3: if p[i]==’*’ 

  • There are two choices - 
    • We can match this ‘*’ to an empty sequence and move on to the next character in the pattern.
    • Match ‘*’ with a sequence of characters starting with the current character of the text string. Therefore, move to the next character in the text string, and the pattern string stays at the same position.

Approach 1: Recursion

Implementation of the above idea using recursion is as follows

  • C++

C++

#include<iostream>
#include <bits/stdc++.h>
using namespace std;


bool isMatch(string s, string p, int i, int j){
//If you have reached the end of the pattern and you also reached the end of the text, then it's a match. Else it's not.
if (j == p.size())
   return (i == s.size());
//Whenever the text string is empty or we're at the end of the string, the
//pattern string can only be matched if it equals '*" because the '*' can be
//replaced by an empty string.
if (i == s.size())
{
   for (int k = j; k < p.size(); k++)
       if (p[k] != '*') return false;


   return true;
}
//If we have a same character or a '?' they simply match so move ahead in both pattern and text.
if ((p[j] == s[i]) || p[j] == '?')
{
   return isMatch(s,p, i + 1, j + 1);
}
if (p[j] == '*')
{
   return isMatch(s, p, i , j + 1) ||  //Ignore the pattern and match with next character in pattern
         isMatch(s, p, i+ 1, j);  //Match multiple characters in string with '*'
}
return false;
}


int main(){
   string s,p;
   cin>>s>>p;
   if(isMatch(s,p,0,0)){
       cout<<"YES"<<endl;
   }
   else{
       cout<<"NO"<<endl;
   }
   return 0;
}

Input

s= adceb
p = *a*b

Output

YES

Time complexity

O(2n), where n is the length of string p and m is the length of string s.

Space complexity

O(n*m), where n is the length of string p and m is the length of string s.

Reason: We’re storing the values of dp for each i and j from 0 to n and 0 to m, respectively. 

Approach 2: Dynamic Programming

We can solve this problem using dynamic programming. So, it’s suggested that you revise this topic once.

If the length of the text string is m and pattern length is n, make a dp table of size (n+1)*(m+1), where dp[i][j] would denote whether the subpattern from index 0 to i-1 can match the substring of text from 0 to j-1. 

The answer for dp[i][j] will depend on the smaller subproblems.

The steps are :

  • Declare a 2-D bool vector named dp of size (n+1)*(m+1) and initialise the values to 0;
  • Base cases:
    • dp[0][0] = 1 because empty strings always match.
    • Whenever the text string is empty, the pattern string can only be matched if it equals ‘*” because the ‘*’ can be replaced by an empty string. So, if text string s ==” “, if p==’*’, we can write for all i from 0 to n dp[i][0] = 1. Else, dp[i][0] = 0.
    • If the pattern string is empty and the text string is not empty, it can never be matched. Therefore, for all i from 0 to m, dp[0][i] = 0;
       
  • Start from i=1 to n and j=1 to n. Recurrence relation is: 
    • If p[i-1] == ‘*’, replace this with an empty sequence and check for dp[i][j-1] or replace this with current character s[j-1] move ahead in s and check for dp[i-1][j].  
    • Else If p[i-1] ==’?’, replace this with the current character and check for the rest, i.e; check for dp[i-1][j-1]. 
    • Else p[i-1] is a character other than the above two, just check if that character is equal to s[j-1] or not. If it is, check for dp[i-1][j-1], otherwise dp[i][j] = false.
       
  • Return dp[n-1][m-1].

Implementation 

Implementation of the above discussed approach:

  • C++

C++

#include<iostream>
#include <bits/stdc++.h>
using namespace std;


bool isMatch(string s, string p) {
   int m = s.length(); //length of string s
   int n = p.length(); //length of string p
   vector<vector<bool>> dp(n+1, vector<bool>(m+1, false)); //declaration of dp vector
   dp[0][0] = true;
   bool flag = true;
   for (int i = 1; i < dp.size(); ++i) {
       if (p[i-1] != '*'){
           flag = false;
       }
       dp[i][0] = flag;
   }
   for (int i = 1; i <= p.size(); ++i) {
       for (int j = 1; j <= s.size(); ++j) {
           if (p[i-1] == '*') {
               if (dp[i-1][j] || dp[i][j-1]){
                   dp[i][j] = true;
               }      
           }
           else if (p[i-1] == '?') {
               if (dp[i-1][j-1] == true){
                   dp[i][j] = true;
               }
           }
           else {
               if(dp[i-1][j-1] == true && p[i-1] == s[j-1]) {
                   dp[i][j] = true;
               }
           }
       }
   }
   return dp[dp.size()-1][dp[0].size()-1];
}


int main(){
   string s,p;
   cin>>s>>p;
   if(isMatch(s,p)){
       cout<<"YES"<<endl;
   }
   else{
       cout<<"NO"<<endl;
   }
   return 0;
}

Input

s= adceb
p = *a*b

 

Output

true

Time complexity

O(n*m), where n is the length of string p and m is the length of string s.

Reason: Because we’re calculating the value of dp for each i and j from 0 to n and 0 to m, respectively. 

Space complexity

O(n*m), where n is the length of string p and m is the length of string s.

Reason: We’re storing the values of dp for each i and j from 0 to n and 0 to m, respectively. 

Frequently asked questions

What are the two types of wildcards?

Two distinct kinds of wildcards: An asterisk can be used to represent any string of characters, even an empty string. The question mark (?) is a wildcard that stands in for any single character.

What is the difference between match and wildcard?

A match is just a straightforward string comparison in which the two strings must exactly match. A pattern matching process in which the pattern may contain wildcards is known as a wildcard match.

How do you match wildcards?

You can employ several techniques to match wildcards, including Regular expressions and functions. Functions for matching wildcards are included in various programming languages and libraries.

What is the difference between wildcard matching and regular expression matching?

While both techniques deal with pattern matching in text, they differ in complexity and expressiveness:

  • Wildcard matching: Simpler and uses fewer characters (* and ?). Offers basic matching for unknown characters.
  • Regular expression matching: More powerful and utilizes a wider range of special characters and constructs. Allows for complex pattern matching beyond simple wildcard substitutions.

Conclusion

In this article, we’ve discussed the wildcard matching problem. Here an effective method has been used, which is called dynamic programming. This is a crucial topic, and there are numerous exciting problems related to this topic.

Recommended problems

Tower of Hanoi

minimum cost to convert to the given string, and

 rod cutting problem

Do check out The Interview guide for Product Based Companies as well as some of the popular Interview problems from top tech companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Refer to our Guided Path to upskill yourself in DSACompetitive ProgrammingJavaScriptSystem Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio!

Happy Learning!

Previous article
Minimum insertion to convert the string to a palindrome
Next article
Best time to buy and sell stock II
Live masterclass