Leetcode Wildcard Matching problem solution

YASH PAL, 31 July 202418 January 2026

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:

‘?’ Matches any single character.
‘*’ Matches any sequence of characters (including the empty sequence).
The matching should cover the entire input string (not partial).

Leetcode Wildcard Matching problem solution

Leetcode Wildcard Matching 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]

Wildcard Matching 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 solutions Leetcode Problems Solutions Leetcode

Leave a Reply