# Wildcard Matching

This page explains Java solution to problem `Wildcard Matching` using `Dynamic Programming`.

## Problem Statement

Given an input string `s` and a pattern `p`, implement wildcard pattern matching with support for `?` and `*`.

• `?` Matches any single character.
• `*` Matches any sequence of characters (including the empty sequence)
Example 1:

Input: s = "adceb", p = "*a*b"
Output: true

Example 2:

Input: s = "acdcb", p = "a*c?b"
Output: false

## Solution

If you have any suggestions in below code, please create a pull request by clicking here.
``````
package com.vc.hard;

class WildcardMatching {
public boolean isMatch(String s, String p) {
if(s == null && p == null) return true;
else if(s == null || p == null) return false;

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

## Time Complexity

O(M * N)
Where M is length of input string s
And N is length of input string p

## Space Complexity

O(M * N) Where M is length of input string s
And N is length of input string p