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


If You Like This Page Then Make Sure To Follow Us on Facebook, G News and Subscribe Our YouTube Channel. We will provide you updates daily.
Shares
facebook sharing button Share
twitter sharing button Tweet
whatsapp sharing button Share
telegram sharing button Share
pinterest sharing button Pin

Leave a Comment