Wildcard Matching LeetCode Solution

Here, We see Wildcard Matching problem Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc., with different approaches.

Wildcard Matching LeetCode Solution

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'.

• C++ Solution
• Java Solution
• JavaScript Solution
• Python Solution

Wildcard Matching Leetcode Solution 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];       
    }
};
Code language: C++ (cpp)

Wildcard Matching Leetcode Solution 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()];     
    }
}
Code language: Java (java)

Wildcard Matching Leetcode Solution 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]    
};
Code language: jboss-cli (jboss-cli)

Wildcard Matching Leetcode Solution 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]
Code language: Python (python)