Solution For Wildcard Matching
The Wildcard Matching problem on Leetcode asks for an algorithm to determine if a given string s matches a given pattern p, where the pattern includes the special characters ‘?’ (matching any single character) and ‘*’ (matching any sequence of characters, including an empty sequence).
To solve this problem, we can use dynamic programming with a two-dimensional boolean array dp, where dp[i][j] represents whether the first i characters of s match the first j characters of p. The base case is dp[0][0] = True, because an empty string matches an empty pattern.
For each i from 0 to the length of s, we iterate through each j from 0 to the length of p, and update dp[i][j] based on the following cases:
If p[j-1] is a non-special character, we require that s[i-1] and p[j-1] match exactly, so dp[i][j] = dp[i-1][j-1] and s[i-1] == p[j-1].
If p[j-1] is a ‘?’ character, we can match any single character, so dp[i][j] = dp[i-1][j-1].
If p[j-1] is a ‘*’ character, we can either match zero characters (dp[i][j-1]) or match one or more characters (dp[i-1][j]) in s. Therefore, dp[i][j] = dp[i-1][j] or dp[i][j-1].
The final result is dp[length of s][length of p], which represents whether the entire s matches the entire p.
Here is the Python implementation of the solution:
def isMatch(s: str, p: str) -> bool:
dp = [[False](len(p)+1) for _ in range(len(s)+1)]
dp[0][0] = True
for j in range(1, len(p)+1):
if p[j-1] == ‘‘:
dp[0][j] = dp[0][j-1]
for i in range(1, len(s)+1):
for j in range(1, len(p)+1):
if p[j-1] != ‘*’:
dp[i][j] = dp[i-1][j-1] and (s[i-1] == p[j-1] or p[j-1] == ‘?’)
else:
dp[i][j] = dp[i-1][j] or dp[i][j-1]
return dp[len(s)][len(p)]
The time complexity of this solution is O(len(s) * len(p)), and the space complexity is also O(len(s) * len(p)) due to the dp array.
Step by Step Implementation For Wildcard Matching
class Solution { public boolean isMatch(String s, String p) { // base case if (p.length() == 0) { return s.length() == 0; } // special case if (p.equals(s) || p.equals("*")) { return true; } // if the first character of p is not '*', then it must match // the first character of s if (p.charAt(0) != '*') { if (s.length() == 0 || (p.charAt(0) != '?' && p.charAt(0) != s.charAt(0))) { return false; } return isMatch(s.substring(1), p.substring(1)); } // if we reach here, it means the first character of p is '*' // we need to check every possible match of this '*' with s while (s.length() > 0) { if (isMatch(s, p.substring(1))) { return true; } s = s.substring(1); } return isMatch(s, p.substring(1)); } }
class Solution: def isMatch(self, s: str, p: str) -> bool: # base case: if p == s or p == "*": return True # if p is empty if p == "": return False # if s is empty if s == "": # check if p consists only of "*" for i in range(len(p)): if p[i] != "*": return False return True # recursive case 1: when the first characters of p and s match if p[0] == s[0] or p[0] == "?": return self.isMatch(s[1:], p[1:]) # recursive case 2: when the first character of p is "*" if p[0] == "*": # check if "*" matches with empty string if self.isMatch(s, p[1:]): return True # check if "*" matches with non-empty string for i in range(1, len(s)+1): if self.isMatch(s[i:], p[1:]): return True return False
var isMatch = function(s, p) { let dp = new Array(s.length + 1).fill(0).map(() => new Array(p.length + 1).fill(false)); dp[0][0] = true; for (let i = 1; i <= p.length; i++) { if (p[i-1] == '*') { dp[0][i] = dp[0][i-1]; } } for (let i = 1; i <= s.length; i++) { for (let j = 1; j <= p.length; j++) { if (p[j-1] == '*') { dp[i][j] = dp[i-1][j] || dp[i][j-1]; } else if (p[j-1] == '?' || p[j-1] == s[i-1]) { dp[i][j] = dp[i-1][j-1]; } } } return dp[s.length][p.length]; };
class Solution { public: bool isMatch(string s, string p) { int m = s.length(), n = p.length(); bool dp[m+1][n+1]; memset(dp, false, sizeof dp); dp[0][0] = true; for (int i = 1; i <= n; i++) if (p[i-1] == '*') dp[0][i] = dp[0][i-1]; for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (p[j-1] == '*') dp[i][j] = dp[i-1][j] || dp[i][j-1]; else if (s[i-1] == p[j-1] || p[j-1] == '?') dp[i][j] = dp[i-1][j-1]; } } return dp[m][n]; } };
public class Solution { public bool IsMatch(string s, string p) { // edge case - if the pattern is empty, the only way to match is if the input string is also empty if(p.Length == 0) { return s.Length == 0; } // edge case - if the pattern is "*" then it will match any input string if(p.Equals("*")) { return true; } // edge case - if the input string is empty, the only way to match is if the pattern is also empty or consists only of "*" characters if(s.Length == 0) { foreach(char c in p) { if(c != '*') { return false; } } return true; } // dp[i][j] will be true if the first i characters in the input string can be matched by the first j characters in the pattern bool[][] dp = new bool[s.Length + 1][]; for(int i = 0; i <= s.Length; i++) { dp[i] = new bool[p.Length + 1]; } // since we are iterating over the dp array from left to right and top to bottom, we can initialize the first row and column here dp[0][0] = true; for(int i = 1; i <= p.Length; i++) { if(p[i - 1] == '*') { dp[0][i] = dp[0][i - 1]; } } for(int i = 1; i <= s.Length; i++) { for(int j = 1; j <= p.Length; j++) { // if the current characters in the input string and pattern match, or if the current character in the pattern is a '?', // then we can take the value from the cell to the left and top (dp[i-1][j-1]) if(s[i - 1] == p[j - 1] || p[j - 1] == '?') { dp[i][j] = dp[i - 1][j - 1]; } // if the current character in the pattern is a '*', then we can take the value from the cell to the left (dp[i][j-1]) // or we can take the value from the cell above (dp[i-1][j]) else if(p[j - 1] == '*') { dp[i][j] = dp[i][j - 1] || dp[i - 1][j]; } // otherwise, the characters don't match and we can't take the value from any other cell, so the value in this cell is false else { dp[i][j] = false; } } } // the value in the bottom right cell of the dp array will be the answer return dp[s.Length][p.Length]; } }