Wildcard Matching Problem Solution

Wildcard Matching Problem: Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*' where:

• '?' Matches any single character.
• '*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

Example :

Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Wildcard Matching Problem Solution

Problem Solution In Python

class Solution(object):
    def isMatch(self, s, p):
        dp = [[False for i in range(len(p)+1)] for j in range(len(s)+1)]
        dp[0][0] = True
        
        s = "#" + s
        p = "#" + p
        
        for j in range(1, len(dp[0])):
            if p[j] == "*":
                dp[0][j] = dp[0][j-1]
        

        
        for i in range(1, len(dp)):
            for j in range(1, len(dp[0])):
                if s[i] == p[j] or p[j] == "?":
                    dp[i][j] = dp[i-1][j-1]
                elif p[j] == "*":
                    dp[i][j] = (dp[i-1][j-1] or dp[i][j-1] or dp[i-1][j])

        return dp[-1][-1]

Problem Solution In Java

class Solution {
    public boolean isMatch(String s, String p) {
       Boolean[][] dp = new Boolean[s.length()][p.length()];
       return match(s, p, 0, 0, dp); 
    }
    
    public boolean match(String s, String p, int i, int j, Boolean[][] dp) {
        if(i >= s.length() && j >= p.length()) {
            return true;
        }
        if(i >= s.length() && p.charAt(j) == '*') {
            return match(s, p, i, j+1, dp);
        }
        if(i >= s.length()) {
            return false;
        }
        if(j >= p.length()) {
            return false;
        }
        if(dp[i][j] != null) return dp[i][j];
        if(p.charAt(j) == '*') {
            dp[i][j] = match(s, p, i+1, j+1, dp) || match(s, p, i+1, j, dp) || match(s, p, i, j+1, dp);
        } else if(p.charAt(j) == s.charAt(i)) {
            dp[i][j] = match(s, p, i+1, j+1, dp);
        } else if(p.charAt(j) == '?'){
            dp[i][j] = match(s, p, i+1, j+1, dp);
        }else{ 
            dp[i][j] = false;
        }
        return dp[i][j];
    }
}

Problem Solution In C++

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

Problem Solution In C

bool isMatch(char * s, char * p)
{
    int len_s = strlen(s);
    int len_p = strlen(p);

    int t_rows = len_p + 1;
    int t_cols = len_s + 1;
    int t_len = t_rows * t_cols;

    bool* table = (bool*)malloc(t_len * sizeof(bool));
    memset(table, 0, t_len * sizeof(bool));

    int pos = 0;

    for (int i = 0; i < t_rows; i++) {
        for (int j = 0; j < t_cols; j++) {
            if (i == 0) {
                if (j == 0) {
                    table[0] = true;
                }
                pos++;
                continue;
            }

            if (p[i - 1] == '*') {
                if (table[pos - t_cols] == true ||
                    (j > 0 && table[pos - 1] == true))
                {
                    table[pos] = true;
                }
            } else if (p[i - 1] == '?') {
                if (j > 0 && table[pos - t_cols - 1] == true)
                {
                    table[pos] = true;
                }
            } else {
                if (j > 0 && table[pos - t_cols - 1] == true &&
                    p[i - 1] == s[j - 1])
                {
                    table[pos] = true;
                }
            }

            pos++;
        }
    }
    
    return table[pos - 1];
}