Leetcode Wildcard Matching problem solution

YASH PAL,

In this Leetcode Wildcard Matching problem solution we have given an input string (s) and a pattern (p), implement wildcard pattern matching with support for ‘?’ and ‘*’ where:

  1. ‘?’ Matches any single character.
  2. ‘*’ Matches any sequence of characters (including the empty sequence).
  3. The matching should cover the entire input string (not partial).
Leetcode 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];
}

coding problems