# 44. Wildcard Matching (Hard)

https://leetcode.com/problems/wildcard-matching/

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).
```

The matching should cover the entire input string (not partial).

Note:

• `s` could be empty and contains only lowercase letters `a-z`.
• `p` could be empty and contains only lowercase letters `a-z`, and characters like `?` or `*`.

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

Example 4:

```Input:
p = "*a*b"
Output: true
Explanation: The first '*' matches the empty sequence, while the second '*' matches the substring "dce".
```

Example 5:

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

## Solutions

``````class Solution {

// Used to keep the matching results of already compared strings, otherwise,
// it will exceeds time limit.
Map<String, Boolean> track = new HashMap<>();

public boolean isMatch(String s, String p) {
if (s == null) {
s = "";
}

if (p == null) {
p = "";
}

String np = "";
char pre = 0;

// process p to merge consecutive *
for (int i = 0; i < p.length(); i++) {

// initialize the start condition
if (i == 0) {
np += p.charAt(0);
pre = p.charAt(0);

continue;
}

if (p.charAt(i) == pre && pre == '*') {
continue;
}

// if not consecutive *, move on
np += p.charAt(i);
pre = p.charAt(i);
}

return check(s, np);
}

private boolean check(String s, String p) {
/*
// if two string match, return immediately
if (isFound) {
return isFound;
}
*/

boolean ans = false;

if (s.length() == 0 && p.length() == 0) {
return true;
}

if (s.length() != 0 && p.length() == 0) {
return false;
}

if (track.containsKey(s + "#" + p)) {
return track.get(s + "#" + p);
}

if (s.length() == 0 && p.length() != 0) {

// After processing, p will not contain consecutive *, in other words, if p.length() > 1
// there must be some other chars that need to be matching 1 by 1. Since s.length() is 0,
// nothing to compare. Only if p.length() == 1 and p[0] = '*', p and s can match perfectly.

if (p.length() == 1 && p.charAt(0) == '*') {
ans = true;
} else {
ans = false;
}

track.put(s + "#" + p, ans);

return ans;
}

// To reach here, s.length and p.length both >= 1

// count chars except *
int charCount = 0;
for (int i = 0; i < p.length(); i++) {
if (p.charAt(i) != '*') {
charCount++;
}
}

// if p contains more regular chars, impossible to match them all
if (charCount > s.length()) {
ans = false;

track.put(s + "#" + p, ans);

return ans;
}

// if p[0] != '.' and '*', test if p[0] == s[0]
if (p.charAt(0) != '?' && p.charAt(0) != '*') {

if (s.charAt(0) != p.charAt(0)) {
// return false if not match

ans = false;
} else {
// check recursively if match

ans = check(s.substring(1), p.substring(1));
}

track.put(s + "#" + p, ans);

return ans;
}

// if p[0] == '.', no need to test if p[0] == s[0]
// move on to compare s[1:] p[1:]
if (p.charAt(0) == '?') {
ans = isMatch(s.substring(1), p.substring(1));

track.put(s + "#" + p, ans);

return ans;
}

// if p[0] == '*', three situations,

// 1. compare s[], p[1:] which means p[0] covers zero char

// 2. s[1:] p[1:] which p[0] covers 1 char and its coverage ends here.

// 3. compare s[1:], p[:] which means p[0] matches at least 2 chars and
// the followup letters will still be covered.

if (p.charAt(0) == '*') {
// p[0] counts for 0 char
ans = ans || check(s, p.substring(1));

// p[0] counts for 1 char
ans = ans || check(s.substring(1), p.substring(1));

// p[0] counts for at least 2 char
ans = ans || check(s.substring(1), p);
}

// any true results of above three matching test will result in a final true

track.put(s + "#" + p, ans);

return ans;
}
}
``````