Wildcard Matching

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:

  1. 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].

  2. If p[j-1] is a ‘?’ character, we can match any single character, so dp[i][j] = dp[i-1][j-1].

  3. 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];
    }
}


Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]