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 lettersa-z
.p
could be empty and contains only lowercase lettersa-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: s = "adceb" 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;
}
}