Wildcard Matching Editorial

Practice Problem Link: Wildcard Matching

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Implement wildcard matching.

In a wildcard string:

• a-z matches the corresponding character.
• ? matches any single character.
• * matches any sequence of characters (incl. empty sequence).

The entire input string should be matched.

The function would take a string s and the wildcard pattern p.

Naive Approach

The naive approach is to use a recursive brute force approach, to check all the possible lengths of both the strings, and all the possible cases of a character being a ‘*’, ‘?’, or not a wildcard character. Recursively we can try out all the possibilities for both the strings, and check if any of the possible choices of characters, allows both the strings to match completely. If yes, we return true, else after trying out all the possibilities we return false. The cases to be considered are: 

• The current character is not a wildcard character: If the characters in both the strings don't match, we immediately return false. Else, we move one character ahead in both the strings for processing.
• The current character is a ‘*’: Ignore the current character and move on to the next one, or assign the next character in the string to this wildcard character.
• The current character is a ‘?’ : Ignore the current character.

Analysis

• Time Complexity: Exponential
• Space Complexity: O(1) // If recursion stack space is ignored.

Implementation

C++

bool solve(string s, string p, int n, int m) {
	if(n == s.length() && m == p.length()) {
		return true;
	}
	if(n == s.length()) {
		for(int k = m; k < p.length(); k++) {
			if(p[k] != '*') {
				return false;
			}
		}
		return true;
	}
	if(m == p.length()) {
		return false;
	}
	bool matched = false;
	if(p[m] == '?' || s[n] == p[m]) {
		matched = solve(s, p, n + 1, m + 1);
	}
	else if(p[m] == '*') {
		matched = solve(s, p, n + 1, m) | solve(s, p, n, m + 1);
	}
	return matched;
}
bool isMatch (string s, string p) {
	return solve(s, p, 0, 0);
}

Java

class Solution {
	boolean solve(char[] s, char[] p, int n, int m) {
		if(n == s.length && m == p.length) {
			return true;
		}
		if(n == s.length) {
			for(int k = m; k < p.length; k++) {
				if(p[k] != '*') {
					return false;
				}
			}
			return true;
		}
		if(m == p.length) {
			return false;
		}
		boolean matched = false;
		if(p[m] == '?' || s[n] == p[m]) {
			matched = solve(s, p, n + 1, m + 1);
		}
		else if(p[m] == '*') {
			matched = solve(s, p, n + 1, m) | solve(s, p, n, m + 1);
		}
		return matched;
	}
	boolean isMatch (String s, String p) {
		char[] sToChar = s.toCharArray();
		char[] pToChar = p.toCharArray();
		return solve(sToChar, pToChar, 0, 0);
	}  	
}

Optimal Approach

We observe that in the naive solution, multiple function calls are being raised again and again. We can memoize those recursive function calls using DP to prevent those recursive calls from happening again and again, and reduce the complexity of the problem to polynomial time complexity.

Analysis:

• Time Complexity: (|s| * |p|)
• Space Complexity: (|s| * |p|)

Implementation(Recursive)

C++

vector<vector<int>> dp;
bool solve(string s, string p, int n, int m) {
	if(n == s.length() && m == p.length()) {
		return true;
	}
	if(n == s.length()) {
		for(int k = m; k < p.length(); k++) {
			if(p[k] != '*') {
				return false;
			}
		}
		return true;
	}
	if(m == p.length()) {
		return false;
	}
	if(dp[n][m] != -1) {
		return (bool)dp[n][m];
	}
	bool matched = false;
	if(p[m] == '?' || s[n] == p[m]) {
		matched = solve(s, p, n + 1, m + 1);
	}
	else if(p[m] == '*') {
		matched = solve(s, p, n + 1, m) | solve(s, p, n, m + 1);
	}
	return dp[n][m] = matched;
}
bool isMatch (string s, string p) {
	dp.assign(s.length() + 1, vector<int> (p.length() + 1, -1));
	return solve(s, p, 0, 0);
}

Java

class Solution {
	Boolean[][] dp;
	boolean solve(char[] s, char[] p, int n, int m) {
		if(n == s.length && m == p.length) {
			return true;
		}
		if(n == s.length) {
			for(int k = m; k < p.length; k++) {
				if(p[k] != '*') {
					return false;
				}
			}
			return true;
		}
		if(m == p.length) {
			return false;
		}
		if(dp[n][m] != null) {
			return dp[n][m];
		}
		boolean matched = false;
		if(p[m] == '?' || s[n] == p[m]) {
			matched = solve(s, p, n + 1, m + 1);
		}
		else if(p[m] == '*') {
			matched = solve(s, p, n + 1, m) | solve(s, p, n, m + 1);
		}
		return dp[n][m] = matched;
	}
	boolean isMatch (String s, String p) {
		char[] sToChar = s.toCharArray();
		char[] pToChar = p.toCharArray();
		dp = new Boolean[s.length() + 1][p.length() + 1];
		return solve(sToChar, pToChar, 0, 0);
	}  	
}

Implementation(Iterative)

C++

bool isMatch (string s, string p) {
	int n = s.size();
	int m = p.size();
	bool dp[n + 1][m + 1];
	memset(dp, false, sizeof(dp));
	dp[0][0] = true;
	for(int i = 1; i <= m; i++) {
		if(p[i - 1] == '*') {
			dp[0][i] = dp[0][i - 1];
		}
		else {
			dp[0][i] = false;
		}
	}
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			if(p[j - 1] == '?' || (p[j - 1] == s[i - 1])) {
				dp[i][j] = dp[i - 1][j - 1];
			}
			else if(p[j - 1] == '*') {
				dp[i][j] = dp[i - 1][j] | dp[i][j - 1];
			}
			else {
				dp[i][j] = false;
			}
		}
	}
    return dp[n][m];
}

Java

class Solution {
	boolean isMatch (String s, String p) {
	   	int n = s.length();
		int m = p.length();
		boolean[][] dp = new boolean[n + 1][m + 1];
		dp[0][0] = true;
		for(int i = 1; i <= m; i++) {
			if(p.charAt(i - 1) == '*') {
				dp[0][i] = dp[0][i - 1];
			}
			else {
				dp[0][i] = false;
			}
		}
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= m; j++) {
				if(p.charAt(j - 1) == '?' || (p.charAt(j - 1) == s.charAt(i - 1))) {
					dp[i][j] = dp[i - 1][j - 1];
				}
				else if(p.charAt(j - 1) == '*') {
					dp[i][j] = dp[i - 1][j] | dp[i][j - 1];
				}
				else {
					dp[i][j] = false;
				}
			}
		}
		return dp[n][m];
	}
}