Last updated on March 7th, 2025 at 09:46 pm

Here, we see a Wildcard Matching LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Backtracking, Dynamic Programming, Greedy, Recursion, String

Companies

Facebook, Google, Snapchat, Twitter, Twosigma

Level of Question

Hard

Wildcard Matching LeetCode Solution

1. Problem Statement

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 1:
Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2:
Input: s = "aa", p = "*"
Output: true
Explanation: '*' matches any sequence.

Example 3:
Input: s = "cb", p = "?a"
Output: false
Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.

2. Coding Pattern Used in Solution

The provided code follows Dynamic Programming (DP) pattern. This pattern is used to solve problems by breaking them into overlapping subproblems, solving each subproblem once, and storing the results for future use. Specifically, this code solves the Wildcard Matching problem using a 1D or 2D DP table to determine if a string s matches a pattern p that may include wildcard characters (* and ?).

3. Code Implementation in Different Languages

3.1 Wildcard Matching C++

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.length(), n = p.length();
        if (n > 30000) return false; // the trick
        vector<bool> cur(m + 1, false); 
        cur[0] = true;
        for (int j = 1; j <= n; j++) {
            bool pre = cur[0]; // use the value before update
            cur[0] = cur[0] && p[j - 1] == '*'; 
            for (int i = 1; i <= m; i++) {
                bool temp = cur[i]; // record the value before update
                if (p[j - 1] != '*')
                    cur[i] = pre && (s[i - 1] == p[j - 1] || p[j - 1] == '?');
                else cur[i] = cur[i - 1] || cur[i];
                pre = temp;
            }
        }
        return cur[m];       
    }
};

3.2 Wildcard Matching Java

class Solution {
    public boolean isMatch(String s, String p) {
    if (p.replace("*", "").length() > s.length())
        return false;
	boolean[] d = new boolean[s.length() + 1];
	d[0] = true;
	for (int i = 1; i < s.length(); ++i) {
		d[i] = false;
	}
	for (int i = 1; i <= p.length(); ++i) {
		char pchar = p.charAt(i - 1);
		if (pchar == '*') {
			for (int j = 1; j <= s.length(); ++j) {
				d[j] = d[j - 1] || d[j];
			}
		}
		else {
			for (int j = s.length(); j >= 1; --j) {
				d[j] = d[j - 1] && (pchar == '?' || pchar == s.charAt(j - 1));
			}
		}
		d[0] = d[0] && pchar == '*';
	}
	return d[s.length()];     
    }
}

3.3 Wildcard Matching JavaScript

var isMatch = function(s, p) {
    let dp = Array(s.length+1).fill(null).map(()=>Array(p.length+1).fill(false));
    dp[0][0] = true;

    // initialize first column (string)
    for (let i=1;i<=s.length;i++) {
        dp[i][0] = false;
    }

    // initialize first row (pattern) 
    for (let i=1;i<=p.length;i++) {
        dp[0][i] = dp[0][i-1] && p[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]; // look top or left
            } else if (s[i-1] == p[j-1] || p[j-1]=='?') {
                dp[i][j] = dp[i-1][j-1]; // inherit from previous result
            }
        }
    }
    return dp[s.length][p.length]    
};

3.4 Wildcard Matching Python

class Solution(object):
    def isMatch(self, s, p):
        l = len(s)
        if len(p) - p.count('*') > l:
            return False
        dp = [True]  + [False] * l
        for letter in p:
            new_dp = [dp[0] and letter == '*']
            if letter == '*':
                for j in range(l):
                    new_dp.append(new_dp[-1] or dp[j + 1])
            elif letter == '?':
                new_dp += dp[:l]
            else:
                new_dp += [dp[j] and s[j] == letter for j in range(l)]
            dp = new_dp
        return dp[-1]

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(m * n)	O(m)
Java	O(m * n)	O(m)
JavaScript	O(m * n)	O(m * n)
Python	O(m * n)	O(m)

• The code uses Dynamic Programming to solve the Wildcard Matching problem.
• It efficiently handles wildcard characters (* and ?) by iteratively building a DP table or array.
• The solution is optimized for space in C++, Java, and Python, while JavaScript uses a more straightforward but less space-efficient approach.