Wildcard Pattern Matching | Dynamic Programming Tutorials | Part 22

Hello guys, welcome back to “code with asharam”. First of all, I am really sorry for not writing anything for last 72 hours. Actually, I had 2 quizes in 2 consecutive days and thanks to me, they went horrible. Okay! so, this is 22nd part of my dynamic programming tutorials. I will discuss Wildcard Pattern Matching this time. If at any moment it feels like that things are going over your head, then, I advice to go through all the last tutorials. Even after that if you are stuck somewhere, then, feel free to leave a comment or send me a mail. I will answer your query as soon as possible. Wildcard matching has a lot of application in real word. You will come across it if you will ever work with databases. So, without any further delay, let’s take a dive into deep oceans of dynamic programming.

Wildcard Pattern Matching

Given a text S and a wildcard pattern P, implement wildcard pattern matching algorithm that finds if wildcard pattern is matched with text. The matching should cover the entire text (not partial text).

The wildcard pattern can include the characters ‘?’ and ‘*’
‘?’ – matches any single character
‘*’ – Matches any sequence of characters (including the empty sequence)

Problem statement source :- geeksforgeeks

Give it a try on your own before moving forward

Approaching the problem

Till now you would have glued it to your memory that our way of solving problems using dynamic programming is an universal constant. We will play our game of guessing what is happening, what can or what cannot happen? Before moving forward, I will state that match(i, j) returns true if first i characters of pattern matches with first j characters of text and otherwise it returns false. Now, If we are at we are at ith and jth character of pattern and text respectively, then, there can be following possiblities:

  1. We encounter a ‘?’ in the pattern. Since ‘?’ (P[i]) can be matched with only a single character (S[j]) of text , P[1…i] will match with S[1…j] if and only if P[1…i-1] matches with S[1…j-1]. In the language of algorithms, we can say:
    match(i, j) = match(i-1, j-1) if P[i] == '?'
  2. We do not encounter any special character in the pattern. In that case, P[1…i] will match with S[1…j] if and only if P[1…i-1] matches with S[1…j-1] and P[i] matches with S[j]. Formally, we can write it as:
    match(i, j) = match(i-1, j-1) && P[i]==S[j]  if P[i] not in {'?', '*'}
  3. We encounter a ‘*’ in the pattern. Now, there can further be 2 possibilities:
    1. We match empty sequence with ‘*’. In that case, P[1…i] will match with S[1…j] if and only if P[1…i-1] matches with S[1…j].
    2. We match ‘*’ with S[j]. In that case, P[1…i] will match with S[1…j] if and only if P[1…i] matches with S[1…j-1]. You can appreciate the fact that ‘*’ unlike ‘?’ can be used again for a continuous sequence.

    If any one of the above 2 cases returns true, then, match(i, j) will also return true. Formally speaking,

    match(i, j) = match(i-1, j) || match(i, j-1) if P[i] == '*'

Base cases and Memoization

We just need to combine last 3 statements together to complete our algorithm. But before doing so, we need to find the base cases as without them our recursion will run for eternity. Now, you know that a null text will always match with null pattern, i.e., match(0, 0) = true. Also, if pattern is empty and text is not empty, then, no match is possible, i.e., match(0, i) = false. Finally, if text is empty and pattern is not empty, then, there will be two possibilities:

  1. P[i] == ‘*’. In this case, we can match ‘*’ with empty string and hence, match(i, 0) will depend upon match(i-1, 0).
  2. P[i] != ‘*’. In this case, no match is possible and hence, match(i, 0) will return false.

After finding the base cases, there is one famous obstacle left which is overlapping of subproblems. Since, we can only make length(P)*length(M) distinct function calls, we will use a 2-d array to store the computed result of all function calls. After that we can just use the cached data instead of recomputing the solutions. So, let’s see how our final algorithm looks like:

match(i, j) = true if i==0 && j==0
              false if i==0
              false if j=0 & P[i] != '*'
              dp[i][j] if already computed
              dp[i][j] = match(i-1, j) if j=0 & P[i] == '*'
              dp[i][j] = match(i-1, j-1) if P[i] == '?'
              dp[i][j] = match(i-1, j-1) && P[i] == S[j] if P[i] not in {'?', '*'}
              dp[i][j] = match(i-1, j) || match(i, j-1) otherwise

Let’s write a beautiful code for the beautiful algorithm we have written:

Code

#include <bits/stdc++.h>

using namespace std;

#define MAX 1001

string S, P;
bool dp[MAX][MAX], computed[MAX][MAX];

bool match(int i, int j)
{
    if (i==0 && j==0) return true;
    
    if (i==0) return false;

    if (j==0 && P[i-1] != '*') return false;

    if (computed[i][j]) return dp[i][j];
    
    computed[i][j] = true;

    if (j==0 && P[i-1]=='*') return dp[i][j] = match(i-1, j);

    if (P[i-1]=='?') return dp[i][j] = match(i-1, j-1);

    if (P[i-1]!='?' && P[i-1]!='*')
        return dp[i][j] = match(i-1, j-1) && P[i-1] == S[j-1];

    return dp[i][j] = match(i-1, j) || match(i, j-1);
}

int main()
{
    memset(computed, false, sizeof(computed));
    
    S = "baaabab", P = "**a*****ab";

    cout << match(P.length(), S.length()) << endl;
    
    // output is 1 (true)
    
}

Suggestion :- “****” will do same task as “*”. Hence, you can replace all such substrings with “*” before starting to compute.
Finally, we have solved Wildcard Pattern Matching with time and space complexity of O(length(P)*length(S)).
So, that’s it guys for today. I hope you would have enjoyed this tutorial. If you liked this tutorial, then, please follow my blog and share it with your friends. Meanwhile, don’t forget to solve The christmas gift.
You can subscribe to my YouTube channel for video tutorials on dynamic programming.
You can connect with me on LinkedIn. To get all of your queries answered, you can message me on Quora. Follow me on medium for more of my writings.

Leave a Reply

%d bloggers like this: