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

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

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)