# Leetcode Wildcard Matching problem solution

Mar 24, 2023

In the Leetcode Wildcard Matching problem solution 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’.

Constraints:

• 0 <= s.length, p.length <= 2000
• s contains only lowercase English letters.
• p contains only lowercase English letters, ‘?’ or ‘*’.

## Solution in C Programming

``````bool
isMatch(char *s, char *p) {
size_t len, i;
bool *ans, result;

len = strlen(s);
ans = malloc((len + 1) * sizeof(bool));
memset(ans + 1, 0, len * sizeof(bool));
*ans = true;

for ( ; *p != 0; ++p) {
if (*p == '*') {
for (i = 0; i < len; ++i)
ans[i + 1] |= ans[i];
} else {
for (i = 0; i < len; ++i)
ans[len - i] = ans[len - i - 1] & (s[len - i - 1] == *p || *p == '?');
ans[0] = false;
}
}
result = ans[len];
free(ans);
return result;
}``````

## Solution in C++ Programming

``````class Solution {
public:
bool isMatch(string s, string p) {
int n = s.length();
int m = p.length();
vector<vector<int>> dp(n+1,vector<int>(m+1));
dp[0][0] = 1;
// int flag=0;
for(int i=1;i<=n;i++)
dp[i][0] = 0;
for(int i=1;i<=m;i++)
{
if(p[i-1]=='*')
dp[0][i] = dp[0][i-1];
else
dp[0][i] = 0;
}

for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(s[i-1]==p[j-1] || p[j-1]=='?')
dp[i][j] = dp[i-1][j-1];
else if(p[j-1] == '*')
dp[i][j] = dp[i-1][j] || dp[i][j-1] ;
else
dp[i][j] = 0;
}
}
return dp[n][m];
}
};``````

## Solution in Java Programming

``````public class Solution {
public boolean isMatch(String s, String p) {
int m = s.length(), n = p.length();
int count = 0;
for (int i = 0; i < n; i++) {
if (p.charAt(i) == '*') count++;
}
if (count==0 && m != n) return false;
else if (n - count > m) return false;

boolean[] match = new boolean[m+1];
match[0] = true;
for (int i = 0; i < m; i++) {
match[i+1] = false;
}
for (int i = 0; i < n; i++) {
if (p.charAt(i) == '*') {
for (int j = 0; j < m; j++) {
match[j+1] = match[j] || match[j+1];
}
} else {
for (int j = m-1; j >= 0; j--) {
match[j+1] = (p.charAt(i) == '?' || p.charAt(i) == s.charAt(j)) && match[j];
}
match[0] = false;
}
}
return match[m];
}
}``````

## Solution in Python Programming

``````class Solution(object):
def isMatch(self, s, p):
"""
:type s: str
:type p: str
:rtype: bool
"""
s,p='+'+s,'+'+p  # create two new strings with a char added at the front
m,n=len(s),len(p)
if n-p.count('*')>m:
return False
dp=[[False]*m for _ in xrange(n)] # if dp[i][j], this means s[:j+1] can match p[:i+1]
dp[0][0]=True
for i in xrange(1,n):
dp[i][0]=dp[i-1][0] and p[i]=='*'
if p[i]!='*':
for j in xrange(1,m):
dp[i][j]=dp[i-1][j-1] and (p[i]==s[j] or p[i]=='?')
else:
for j in xrange(1,m):
dp[i][j]=dp[i-1][j] or dp[i][j-1]
return dp[-1][-1]``````

## Solution in C# Programming

``````public class Solution {
public bool IsMatch(string s, string p) {
var dp = new bool[s.Length + 1];
var nextDp = new bool[s.Length + 1];

// Base case: dp(0, 0) = true
dp[0] = true;

// Calculate dp(1, *) and onwards
for (var pLen = 1; pLen <= p.Length; pLen++)
{
for (var sLen = 0; sLen <= s.Length; sLen++)
{
if (p[pLen-1] == '*')
{
nextDp[sLen] = dp[sLen] || (sLen > 0 && nextDp[sLen-1]);
}
else
{
nextDp[sLen] = sLen > 0 && dp[sLen-1] && (p[pLen-1] == '?' || p[pLen-1] == s[sLen-1]);
}
}

// swap the arrays
var t = dp;
dp = nextDp;
nextDp = t;
}

return dp[s.Length];
}
}``````

#### By Neha Singhal

Hi, my name is Neha singhal a software engineer and coder by profession. I like to solve coding problems that give me the power to write posts for this site.