Problem Statement: Wildcard Matching
We are given two strings ‘S1’ and ‘S2’. String S1 can have the following two special characters:
- ‘?’ can be matched to a single character of S2.
- ‘*’ can be matched to any sequence of characters of S2. (sequence can be of length zero or more).
We need to check whether strings S1 and S2 match or not.
Examples
Example:
Disclaimer: Don’t jump directly to the solution, try it out yourself first.
Memoization Approach
Algorithm / Intuition
Intuition:
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.
- 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.
Steps to form the recursive solution:
We will first form the recursive solution by the three points mentioned in the Dynamic Programming Introduction.
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].
We can generalize this as follows:
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.
(i) When the characters match
if(S1[i]==S2[j]),
If 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.
(ii) When the characters don’t match
If the characters don’t match, there are three possible scenarios:
- S1[i] == ‘?’
- S1[i] == ‘*’
- S1[i] is some other character
Let us discuss them one by one:
(i) 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.
(ii) 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.
(iii) 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.
To summarise:
- If S1[i] == ‘?’, return f(i-1,j)
- Else if S1[i] == ‘*’, return f(i-1,j) || f(i,j-1)
- Else 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.
(i) 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.
We can say:
- if(i<0 && j<0), return true.
- if(i<0 && j>=0), return false.
(ii) 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, 2, and 3:
Steps to memoize a recursive solution:
If we draw the recursion tree, we will see that there are overlapping subproblems. In order to convert a recursive solution the following steps will be taken:
- 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.
Code
#include <bits/stdc++.h>
using namespace std;
// Function to check if a substring of S1 contains only '*'
bool isAllStars(string &S1, int i) {
for (int j = 0; j <= i; j++) {
if (S1[j] != '*')
return false;
}
return true;
}
// Function to check if S1 matches S2 using wildcard pattern matching
bool wildcardMatchingUtil(string &S1, string &S2, int i, int j, vector<vector<bool>> &dp) {
// Base Cases
if (i < 0 && j < 0)
return true;
if (i < 0 && j >= 0)
return false;
if (j < 0 && i >= 0)
return isAllStars(S1, i);
// If the result for this state has already been calculated, return it
if (dp[i][j] != -1)
return dp[i][j];
// If the characters at the current positions match or S1 has a '?'
if (S1[i] == S2[j] || S1[i] == '?')
return dp[i][j] = wildcardMatchingUtil(S1, S2, i - 1, j - 1, dp);
else {
if (S1[i] == '*')
// Two options: either '*' represents an empty string or it matches a character in S2
return dp[i][j] = wildcardMatchingUtil(S1, S2, i - 1, j, dp) || wildcardMatchingUtil(S1, S2, i, j - 1, dp);
else
return false;
}
}
// Main function to check if S1 matches S2 using wildcard pattern matching
bool wildcardMatching(string &S1, string &S2) {
int n = S1.size();
int m = S2.size();
// Create a DP table to memoize results
vector<vector<bool>> dp(n, vector<bool>(m, -1));
return wildcardMatchingUtil(S1, S2, n - 1, m - 1, dp);
}
int main() {
string S1 = "ab*cd";
string S2 = "abdefcd";
// Call the wildcardMatching function and print the result
if (wildcardMatching(S1, S2))
cout << "String S1 and S2 do match";
else
cout << "String S1 and S2 do not match";
return 0;
}
import java.util.*;
class TUF {
// Helper function to check if all characters from index 0 to i in S1 are '*'
static boolean isAllStars(String S1, int i) {
for (int j = 0; j <= i; j++) {
if (S1.charAt(j) != '*')
return false;
}
return true;
}
// Recursive function to perform wildcard pattern matching
static int wildcardMatchingUtil(String S1, String S2, int i, int j, int[][] dp) {
// Base Cases
if (i < 0 && j < 0)
return 1; // Both strings are empty, and the pattern matches.
if (i < 0 && j >= 0)
return 0; // S1 is empty, but there are characters left in S2.
if (j < 0 && i >= 0)
return isAllStars(S1, i) ? 1 : 0; // S2 is empty, check if remaining characters in S1 are all '*'.
// If the result is already computed, return it.
if (dp[i][j] != -1) return dp[i][j];
// If the characters match or S1 has a '?', continue matching the rest of the strings.
if (S1.charAt(i) == S2.charAt(j) || S1.charAt(i) == '?')
return dp[i][j] = wildcardMatchingUtil(S1, S2, i - 1, j - 1, dp);
else {
if (S1.charAt(i) == '*') {
// Two possibilities when encountering '*':
// 1. '*' matches one or more characters in S2.
// 2. '*' matches zero characters in S2.
return dp[i][j] = (wildcardMatchingUtil(S1, S2, i - 1, j, dp) == 1 || wildcardMatchingUtil(S1, S2, i, j - 1, dp) == 1) ? 1 : 0;
} else {
// Characters don't match, and S1[i] is not '*'.
return 0;
}
}
}
// Main function to check if S1 matches the wildcard pattern S2
static int wildcardMatching(String S1, String S2) {
int n = S1.length();
int m = S2.length();
int dp[][] = new int[n][m];
for (int row[]: dp)
Arrays.fill(row, -1);
// Call the recursive helper function
return wildcardMatchingUtil(S1, S2, n - 1, m - 1, dp);
}
public static void main(String args[]) {
String S1 = "ab*cd";
String S2 = "abdefcd";
if (wildcardMatching(S1, S2) == 1)
System.out.println("String S1 and S2 do match");
else
System.out.println("String S1 and S2 do not match");
}
}
def isAllStars(S1, i):
# Helper function to check if all characters up to index i in S1 are '*'
for j in range(i + 1):
if S1[j] != '*':
return False
return True
def wildcardMatchingUtil(S1, S2, i, j, dp):
# Base conditions
if i < 0 and j < 0:
return True
if i < 0 and j >= 0:
return False
if j < 0 and i >= 0:
return isAllStars(S1, i)
# If the result for this subproblem is already computed, return it
if dp[i][j] != -1:
return dp[i][j]
if S1[i] == S2[j] or S1[i] == '?':
# Characters match or S1 has a '?'; move to the previous characters in both strings
dp[i][j] = wildcardMatchingUtil(S1, S2, i - 1, j - 1, dp)
elif S1[i] == '*':
# If S1 has a '*', there are two choices:
# 1. '*' represents an empty string in S1, so move to the previous character in S1 (i-1, j).
# 2. '*' represents one or more characters in S1, so move to the previous character in S2 (i, j-1).
dp[i][j] = wildcardMatchingUtil(S1, S2, i - 1, j, dp) or wildcardMatchingUtil(S1, S2, i, j - 1, dp)
else:
dp[i][j] = False # Characters don't match, and S1[i] is not '*'
return dp[i][j]
def wildcardMatching(S1, S2):
n = len(S1)
m = len(S2)
# Initialize a 2D DP array with -1 values
dp = [[-1 for _ in range(m)] for _ in range(n)]
# Calculate and return the result of wildcard matching
return wildcardMatchingUtil(S1, S2, n - 1, m - 1, dp)
def main():
S1 = "ab*cd"
S2 = "abdefcd"
if wildcardMatching(S1, S2):
print("String S1 and S2 do match")
else:
print("String S1 and S2 do not match")
if __name__ == "__main__":
main()
function isAllStars(S1, i) {
for (let j = 0; j <= i; j++) {
if (S1[j] !== '*') {
return false;
}
}
return true;
}
// Function to perform wildcard pattern matching
function wildcardMatchingUtil(S1, S2, i, j, dp) {
// Base Conditions
if (i < 0 && j < 0) {
return true;
}
if (i < 0 && j >= 0) {
return false;
}
if (j < 0 && i >= 0) {
return isAllStars(S1, i);
}
// Check if the result for the current indices is already calculated
if (dp[i][j] !== -1) {
return dp[i][j];
}
if (S1[i] === S2[j] || S1[i] === '?') {
return dp[i][j] = wildcardMatchingUtil(S1, S2, i - 1, j - 1, dp);
} else {
if (S1[i] === '*') {
return dp[i][j] = wildcardMatchingUtil(S1, S2, i - 1, j, dp) || wildcardMatchingUtil(S1, S2, i, j - 1, dp);
} else {
return false;
}
}
}
// Function to perform wildcard pattern matching
function wildcardMatching(S1, S2) {
const n = S1.length;
const m = S2.length;
// Create a 2D array to store dynamic programming values
const dp = new Array(n).fill(null).map(() => new Array(m).fill(-1));
return wildcardMatchingUtil(S1, S2, n - 1, m - 1, dp);
}
// Main function
function main() {
const S1 = "ab*cd";
const S2 = "abdefcd";
// Check if S1 matches S2 using wildcard matching
if (wildcardMatching(S1, S2)) {
console.log("String S1 and S2 do match");
} else {
console.log("String S1 and S2 do not match");
}
}
// Call the main function to start the program
main();
Output: String S1 and S2 do match
Complexity Analysis
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 Approach
Algorithm / Intuition
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.
- First we initialise the dp array of size [n+1][m+1] as zero.
- Next, we set the base condition (keep in mind 1-based indexing), we set the top-left cell as ‘true’, then we set the first column’s value as ‘false’; and for the first row, we will run isAllStars() for every cell value.
- 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.
Code
#include <bits/stdc++.h>
using namespace std;
// Function to check if a substring of S1 contains only '*'
bool isAllStars(string &S1, int i) {
// S1 is taken in 1-based indexing
for (int j = 1; j <= i; j++) {
if (S1[j - 1] != '*')
return false;
}
return true;
}
// Function to perform wildcard pattern matching between S1 and S2
bool wildcardMatching(string &S1, string &S2) {
int n = S1.size();
int m = S2.size();
// Create a DP table to memoize results
vector<vector<bool>> dp(n + 1, vector<bool>(m, false));
// Initialize the first row and column
dp[0][0] = true;
for (int j = 1; j <= m; j++) {
dp[0][j] = false;
}
for (int i = 1; i <= n; i++) {
dp[i][0] = isAllStars(S1, i);
}
// Fill in the DP table
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (S1[i - 1] == S2[j - 1] || S1[i - 1] == '?') {
dp[i][j] = dp[i - 1][j - 1];
} else {
if (S1[i - 1] == '*') {
dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
} else {
dp[i][j] = false;
}
}
}
}
// The value at dp[n][m] contains whether S1 matches S2
return dp[n][m];
}
int main() {
string S1 = "ab*cd";
string S2 = "abdefcd";
// Call the wildcardMatching function and print the result
if (wildcardMatching(S1, S2))
cout << "String S1 and S2 do match";
else
cout << "String S1 and S2 do not match";
return 0;
}
import java.util.*;
class TUF {
// Helper function to check if all characters from index 1 to i in S1 are '*'
static boolean isAllStars(String S1, int i) {
for (int j = 1; j <= i; j++) {
if (S1.charAt(j - 1) != '*')
return false;
}
return true;
}
// Function to perform wildcard pattern matching
static boolean wildcardMatching(String S1, String S2) {
int n = S1.length();
int m = S2.length();
// Create a 2D array to store the matching results
boolean dp[][] = new boolean[n + 1][m + 1];
dp[0][0] = true;
// Initialize the first row and column based on wildcard '*' in S1
for (int j = 1; j <= m; j++) {
dp[0][j] = false;
}
for (int i = 1; i <= n; i++) {
dp[i][0] = isAllStars(S1, i);
}
// Fill the dp array using a bottom-up approach
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (S1.charAt(i - 1) == S2.charAt(j - 1) || S1.charAt(i - 1) == '?') {
dp[i][j] = dp[i - 1][j - 1]; // Characters match or '?' is encountered.
} else {
if (S1.charAt(i - 1) == '*') {
dp[i][j] = dp[i - 1][j] || dp[i][j - 1]; // '*' matches one or more characters.
} else {
dp[i][j] = false; // Characters don't match, and S1[i-1] is not '*'.
}
}
}
}
return dp[n][m]; // The final result indicates whether S1 matches S2.
}
public static void main(String args[]) {
String S1 = "ab*cd";
String S2 = "abdefcd";
if (wildcardMatching(S1, S2)) {
System.out.println("String S1 and S2 do match");
} else {
System.out.println("String S1 and S2 do not match");
}
}
}
def isAllStars(S1, i):
# Helper function to check if all characters up to index i in S1 are '*'
for j in range(1, i + 1):
if S1[j - 1] != '*':
return False
return True
def wildcardMatching(S1, S2):
n = len(S1)
m = len(S2)
# Initialize a 2D DP array dp with dimensions (n+1) x m and fill it with False values
dp = [[False for _ in range(m)] for _ in range(n + 1)]
# Initialize dp[0][0] to True since two empty strings match
dp[0][0] = True
# Initialize the first row of dp
for j in range(1, m):
dp[0][j] = False
# Initialize the first column of dp based on whether S1 consists of all '*' characters up to that position
for i in range(1, n + 1):
dp[i][0] = isAllStars(S1, i)
# Fill in the DP array using dynamic programming
for i in range(1, n + 1):
for j in range(1, m):
if S1[i - 1] == S2[j - 1] or S1[i - 1] == '?':
# Characters match or S1 has a '?'; continue matching with the previous characters
dp[i][j] = dp[i - 1][j - 1]
elif S1[i - 1] == '*':
# If S1 has a '*', there are two choices:
# 1. '*' represents an empty string in S1, so move to the previous character in S1 (i-1, j).
# 2. '*' represents one or more characters in S1, so move to the previous character in S2 (i, j-1).
dp[i][j] = dp[i - 1][j] or dp[i][j - 1]
else:
dp[i][j] = False # Characters don't match, and S1[i-1] is not '*'
# The final value in dp[n][m-1] is True if the two strings match, False otherwise
return dp[n][m-1]
def main():
S1 = "ab*cd"
S2 = "abdefcd"
if wildcardMatching(S1, S2):
print("String S1 and S2 do match")
else:
print("String S1 and S2 do not match")
if __name__ == "__main__":
main()
function isAllStars(S1, i) {
// S1 is taken in 1-based indexing
for (let j = 1; j <= i; j++) {
if (S1[j - 1] !== '*') {
return false;
}
}
return true;
}
// Function to perform wildcard pattern matching
function wildcardMatching(S1, S2) {
const n = S1.length;
const m = S2.length;
// Create a 2D array to store dynamic programming values
const dp = new Array(n + 1).fill(null).map(() => new Array(m + 1).fill(false));
dp[0][0] = true;
for (let j = 1; j <= m; j++) {
dp[0][j] = false;
}
for (let i = 1; i <= n; i++) {
dp[i][0] = isAllStars(S1, i);
}
for (let i = 1; i <= n; i++) {
for (let j = 1; j <= m; j++) {
if (S1[i - 1] === S2[j - 1] || S1[i - 1] === '?') {
dp[i][j] = dp[i - 1][j - 1];
} else {
if (S1[i - 1] === '*') {
dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
} else {
dp[i][j] = false;
}
}
}
}
return dp[n][m];
}
// Main function
function main() {
const S1 = "ab*cd";
const S2 = "abdefcd";
// Check if S1 matches S2 using wildcard matching
if (wildcardMatching(S1, S2)) {
console.log("String S1 and S2 do match");
} else {
console.log("String S1 and S2 do not match");
}
}
// Call the main function to start the program
main();
Output: String S1 and S2 do match
Complexity Analysis
Time Complexity: O(N*M)
Reason: There are two nested loops
Space Complexity: O(N*M)
Reason: We are using an external array of size ‘N*M’. Stack Space is eliminated.
Space Optimization Approach
Algorithm / Intuition
If we closely look the relation,
dp[i][j] = dp[i-1][j-1], dp[i][j] = dp[i-1][j] ||dp[i][j-1]
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.
Approach:
We will space optimize in the following way:
- 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.
- At last, we return prev[m] as our answer.
Code
#include <bits/stdc++.h>
using namespace std;
// Function to check if a substring of S1 contains only '*'
bool isAllStars(string &S1, int i) {
// S1 is taken in 1-based indexing
for (int j = 1; j <= i; j++) {
if (S1[j - 1] != '*')
return false;
}
return true;
}
// Function to perform wildcard pattern matching between S1 and S2
bool wildcardMatching(string &S1, string &S2) {
int n = S1.size();
int m = S2.size();
// Create two arrays to store previous and current rows of matching results
vector<bool> prev(m + 1, false);
vector<bool> cur(m + 1, false);
prev[0] = true; // Initialize the first element of the previous row to true
for (int i = 1; i <= n; i++) {
cur[0] = isAllStars(S1, i); // Initialize the first element of the current row
for (int j = 1; j <= m; j++) {
if (S1[i - 1] == S2[j - 1] || S1[i - 1] == '?') {
cur[j] = prev[j - 1]; // Characters match or S1 has '?'
} else {
if (S1[i - 1] == '*') {
cur[j] = prev[j] || cur[j - 1]; // '*' represents empty or a character
} else {
cur[j] = false; // Characters don't match and S1[i-1] is not '*'
}
}
}
prev = cur; // Update the previous row with the current row
}
// The value at prev[m] contains whether S1 matches S2
return prev[m];
}
int main() {
string S1 = "ab*cd";
string S2 = "abdefcd";
// Call the wildcardMatching function and print the result
if (wildcardMatching(S1, S2))
cout << "String S1 and S2 do match";
else
cout << "String S1 and S2 do not match";
return 0;
}
import java.util.*;
class TUF {
// Helper function to check if all characters from index 1 to i in S1 are '*'
static boolean isAllStars(String S1, int i) {
for (int j = 1; j <= i; j++) {
if (S1.charAt(j - 1) != '*')
return false;
}
return true;
}
// Function to perform wildcard pattern matching
static boolean wildcardMatching(String S1, String S2) {
int n = S1.length();
int m = S2.length();
// Create two boolean arrays to store the matching results for the current and previous rows
boolean[] prev = new boolean[m + 1];
boolean[] cur = new boolean[m + 1];
// Initialize the first element of prev as true
prev[0] = true;
// Iterate through S1 and S2 to fill the cur array
for (int i = 1; i <= n; i++) {
// Initialize the first element of cur based on whether S1 contains '*'
cur[0] = isAllStars(S1, i);
for (int j = 1; j <= m; j++) {
if (S1.charAt(i - 1) == S2.charAt(j - 1) || S1.charAt(i - 1) == '?') {
cur[j] = prev[j - 1]; // Characters match or '?' is encountered.
} else {
if (S1.charAt(i - 1) == '*') {
cur[j] = prev[j] || cur[j - 1]; // '*' matches one or more characters.
} else {
cur[j] = false; // Characters don't match, and S1[i-1] is not '*'.
}
}
}
// Update prev array to store the current values
prev = cur.clone();
}
return prev[m]; // The final result indicates whether S1 matches S2.
}
public static void main(String args[]) {
String S1 = "ab*cd";
String S2 = "abdefcd";
if (wildcardMatching(S1, S2)) {
System.out.println("String S1 and S2 do match");
} else {
System.out.println("String S1 and S2 do not match");
}
}
}
def isAllStars(S1, i):
# Helper function to check if all characters up to index i in S1 are '*'
for j in range(1, i + 1):
if S1[j - 1] != '*':
return False
return True
def wildcardMatching(S1, S2):
n = len(S1)
m = len(S2)
# Initialize two lists, prev and cur, to store the previous and current rows of the DP array
prev = [False for _ in range(m + 1)]
cur = [False for _ in range(m + 1)]
prev[0] = True # Initialize the first element of prev to True
for i in range(1, n + 1):
cur[0] = isAllStars(S1, i) # Initialize the first element of cur based on '*' characters in S1
for j in range(1, m + 1):
if S1[i - 1] == S2[j - 1] or S1[i - 1] == '?':
# Characters match or S1 has a '?'; continue matching with the previous characters
cur[j] = prev[j - 1]
elif S1[i - 1] == '*':
# If S1 has a '*', there are two choices:
# 1. '*' represents an empty string in S1, so move to the previous character in S1 (i-1, j).
# 2. '*' represents one or more characters in S1, so move to the previous character in S2 (i, j-1).
cur[j] = prev[j] or cur[j - 1]
else:
cur[j] = False # Characters don't match, and S1[i-1] is not '*'
prev = cur # Update prev to be the current row
# The final value in prev[m] is True if the two strings match, False otherwise
return prev[m]
def main():
S1 = "ab*cd"
S2 = "abdefcd"
if wildcardMatching(S1, S2):
print("String S1 and S2 do match")
else:
print("String S1 and S2 do not match")
if __name__ == "__main__":
main()
function isAllStars(S1, i) {
// S1 is taken in 1-based indexing
for (let j = 1; j <= i; j++) {
if (S1[j - 1] !== '*') {
return false;
}
}
return true;
}
// Function to perform wildcard pattern matching
function wildcardMatching(S1, S2) {
const n = S1.length;
const m = S2.length;
// Create two arrays, prev and cur, to store dynamic programming values
const prev = new Array(m + 1).fill(false);
const cur = new Array(m + 1).fill(false);
prev[0] = true;
for (let i = 1; i <= n; i++) {
cur[0] = isAllStars(S1, i);
for (let j = 1; j <= m; j++) {
if (S1[i - 1] === S2[j - 1] || S1[i - 1] === '?') {
cur[j] = prev[j - 1];
} else {
if (S1[i - 1] === '*') {
cur[j] = prev[j] || cur[j - 1];
} else {
cur[j] = false;
}
}
}
// Update the prev array with the values from the cur array for the next iteration
for (let j = 0; j <= m; j++) {
prev[j] = cur[j];
}
}
return prev[m];
}
// Main function
function main() {
const S1 = "ab*cd";
const S2 = "abdefcd";
// Check if S1 matches S2 using wildcard matching
if (wildcardMatching(S1, S2)) {
console.log("String S1 and S2 do match");
} else {
console.log("String S1 and S2 do not match");
}
}
// Call the main function to start the program
main();
Output:String S1 and S2 do match
Complexity Analysis
Time Complexity: O(N*M)
Reason: There are two nested loops.
Space Complexity: O(M)
Reason: We are using an external array of size ‘M+1’ to store two rows.
Video Explanation
Special thanks to Anshuman Sharma for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article