LeetCode-in-Java
44. Wildcard Matching
Hard
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’.
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
Constraints:
0 <= s.length, p.length <= 2000scontains only lowercase English letters.pcontains only lowercase English letters,'?'or'*'.
Solution
public class Solution {
public boolean isMatch(String inputString, String pattern) {
int i = 0;
int j = 0;
int starIdx = -1;
int lastMatch = -1;
while (i < inputString.length()) {
if (j < pattern.length()
&& (inputString.charAt(i) == pattern.charAt(j) || pattern.charAt(j) == '?')) {
i++;
j++;
} else if (j < pattern.length() && pattern.charAt(j) == '*') {
starIdx = j;
lastMatch = i;
j++;
} else if (starIdx != -1) {
// there is a no match and there was a previous star, we will reset the j to indx
// after star_index
// lastMatch will tell from which index we start comparing the string if we
// encounter * in pattern
j = starIdx + 1;
// we are saying we included more characters in * so we incremented the
lastMatch++;
// index
i = lastMatch;
} else {
return false;
}
}
boolean isMatch = true;
while (j < pattern.length() && pattern.charAt(j) == '*') {
j++;
}
if (i != inputString.length() || j != pattern.length()) {
isMatch = false;
}
return isMatch;
}
}