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 Falsevar 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];
}
}