Jb Tak Fodega Nhi 🎯 Tb Tk Chodega Nhi 📚 (MAANG)

DPL34 Wildcard Matching 🔥

Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*' where:

'?' Matches any single character.

'*' Matches any sequence of characters (including the empty sequence).

How To Solved this Problem
For every index of string S1, we have different options to match that index with string S2. Therefore, we can think in terms of string matching path as we have done already in previous questions. Again this Problem Based on the DP on String Matching

Either the characters match already.

Or, if there is a ‘?’, we can explicitly match a single character.

For a ‘*’, the following figure explains the scenario.

As there is no uniformity in data, there is no other way to find out than to try out all possible ways. To do so we will need to use recursion.

Recursice Approch

Steps to form the Recursive Solution
Step 1: Express the problem in terms of indexes.

We are given two strings. We can represent them with the help of two indexes i and j. Initially, i=n-1 and j=m-1, where n and m are lengths of strings S1 and S2. Initially, we will call f(n-1,m-1), which means whether string S1[0…n-1] matches with string S2[0…m-1].

Step 2: Try out all possible choices at a given index.

Now, i and j represent two characters from strings S1 and S2 respectively. There are only two options that make sense: either the characters represented by i and j match or they don’t.

Case 1: When the characters match

if(S1[i]==S2[j])

SIf this is true, the characters at i and j match, we can simply move to the next characters of both the strings. So we will just decrement both i and j by 1 and recursively find the answer for the remaining string portions. We return f(i-1,j-1). The following figure makes it clear.

Case 2: When the characters don’t match

if(S1[i] != S2[j]), is true, then we have three possible scenarios let's Check out.

• Case1: S1[i] == ‘?’
• Case2: S1[i] == ‘*’
• Case3: S1[i] is some other character

Case 1: If S1[i] == ‘?’

In this case, we can explicitly match ‘?’ at index i of S1 with the corresponding character at index j of S2. And then recursively call f(i-1,j-1) to check for the remaining string.

Case 2: If S1[i] == ‘*’

This is an interesting case as now ‘*’ can be replaced with any sequence of characters( of length 0 or more) from S2.

We will revisit this example:

If any of these cases return true, we can say that the characters do match. The next question is how to try all possible ways?

We are using two pointers i and j to represent characters of strings S1 and S2. We can surely write a for loop to compare characters from 0 to j of S2 for the above scenario. Can we do it more smartly? Yes, we can. Please understand the approach explained below.

We are using a recursive function f(i,j). If we do only the following two recursive calls:

Call f(i-1,j). i.e replace ‘*’ with nothing and act as if it was not present.

Call f(i,j-1). i.e replace ‘*’ with a single character at index j and make the i pointer to still point at index i. In this, we matched it with a single character (one of the many options that need to be tried) and in the next recursive call, as i still point to ‘*’, we get the exact two recursive calls again.

The following recursive tree will help us to understand the recursion better.

So we see how we can tackle all the required cases associated with ‘*’ by using recursion.

Case 3: If S1[i] is neither ‘?’ nor ‘*’

then we can say as the characters at i and j don’t match then the strings don’t match, so we return false.

Step 3: Return logical OR (||) of all the Choices

If any of the cases return true, we can say that strings do match. We can use OR operator (||) with the recursive calls.

Base Cases We are reducing i and j in our recursive relation, there can be two possibilities, either i becomes -1 or j becomes -1., i,e we exhaust either S1 or S2 respectively.

1. When S1 is exhausted:
When S1 is exhausted (i < 0), we know that in order for the strings to match, String S2 should also exhaust simultaneously. If it does, we return true, else we return false.

if(i < 0 && j < 0), return true.

if(i < 0 && j>= 0), return false.

2. When S2 is exhausted:
When S2 is exhausted(j < 0) and S1 has not, there is only one pattern that can account for true(matching of strings). It is if S1 is like this “*”,”****”,”***”, i.e: S1 contains only stars. Then we can replace every star with a sequence of length 0 and say that the string match.
If S1 is all-stars, we return true, else return false.

The final pseudocode after steps 1, and 2

Time & Space Complexity

Time Complexity: O(2^N)
Reason: Exponential Time we find out the all the Possible Path
Space Complexity: O(N)
Reason: We are using a recursion stack space(O(N))

Memoization Approch

If we Observe in the recursion tree, we will observe a many number of overlapping subproblems. Therefore the recursive solution can be memoized for to reduce the time complexity.

Steps to convert Recursive code to memoization solution:

Create a dp array of size [n][m]. The size of S1 and S2 are n and m respectively, so the variable i will always lie between ‘0’ and ‘n-1’ and the variable j between ‘0’ and ‘m-1’.

We initialize the dp array to -1.

Whenever we want to find the answer to particular parameters (say f(i,j)), we first check whether the answer is already calculated using the dp array(i.e dp[i][j]!= -1 ). If yes, simply return the value from the dp array.

If not, then we are finding the answer for the given value for the first time, we will use the recursive relation as usual but before returning from the function, we will set dp[i][j] to the solution we get.

Time & Space Complexity

Time Complexity:O(N*M)
Reason: There are N*M states therefore at max ‘N*M’ new problems will be solved.
Space Complexity: O(N*M) + O(N+M)
Reason: We are using a recursion stack space(O(N+M)) and a 2D array ( O(N*M)).

Tabulation Approch

Tabulation is a ‘bottom-up’ approach where we start from the base case and reach the final answer that we want and Memoization is the Top-down Approch.

In Tabulation Approch We Just Creat a DP Array Same as Memoization and Simply Convert the Recurance Relation into the form of the Looping

VVVV Important Point: Tabulation Approch is Always 1-Based Indexing Always Remember

Steps to convert Recursive Solution to Tabulation one.

In the recursive logic, we set the base case too if( i < 0 ) and if( j < 0 ) but we can’t set the dp array’s index to -1. Therefore a hack for this issue is to shift every index by 1 towards the right.

To convert the memoization approach to a tabulation one, create a dp array with the same size as done in memoization. We can initialize it as 0. ([n+1][m+1] as zero)

First, we need to initialize the base conditions of the recursive solution, (keep in mind 1-based indexing), we set the first column’s value as i and the first row as j(1-based indexing).

Similarly, we will implement the recursive code by keeping in mind the shifting of indexes, therefore S1[i] will be converted to S1[i-1]. Same for S2.

Similarly, we will implement the recursive code by keeping in mind the shifting of indexes, therefore S1[i] will be converted to S1[i-1]. Same for S2.

At last, we will print dp[N][M] as our answer.

Time & Space Complexity

Time Complexity: O(N*M)
Reason:There are 2 nested loops
Space Complexity: O(N*M)
Reason: We are using an external array of size ‘N*M’. Stack Space is eliminated.

Space Optimization

If we closelly Observed if any Tabulation Approch we used the Some Limited Stuff like: dp[i][j] = dp[i-1][j-1], dp[i][j] = dp[i-1][j] ||dp[i][j-1] for the finding the our ans then definetly here Spaced Optimization is Possible in that types of Problems. Always Remember

Golden Rule

If we required only Prev row and Prev Collom then definetly we can Space Optimized

We see that to calculate a value of a cell of the dp array, we need only the previous row values (say prev) and current row’s previous columns values. So, we don’t need to store an entire array. Hence we can space optimise it.

We take two rows ‘prev’ and ‘cur’

We initialize it to the base condition. We first initialize the prev row. Its first value needs to be true. Rest all the values of the prev row meeds to be false.

Moreover, the cur variable whenever declared should have its first cell’s value given by isAllStarts() function.

Next, we implement the memoization logic. We replace dp[i-1] with prev and dp[i] by cur

After every inner loop execution, we set prev=cur, for the next iteration.

last our ans is prev[m]

Some Important Points:

prev = curr: Some Time not working and not give a Correct answer, same like we face in this Problem due to the Dynamic element Allocation

So we try at the place of the prev = curr

prev[:] = curr

prev = curr[:]

Time & Space Complexity

Time Complexity: O(N*M)
Reason: There are three 2 nested loops
Space Complexity: O(W)
Reason: We are using an external array of size ‘M+1’ to store only one row.