44. Wildcard Matching
Description
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).
Constraints
s
could be empty or contains only lowercase lettersa-z
.p
could be empty or contains only lowercase lettersa-z
, and characters like?
or*
.
Approach
Links
Examples
Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".
Solutions
/**
* Time complexity : O(min(S,P)) for the best case and better than O(SlogP)
* for the average case, where S and P are lengths of the input string
* and the pattern correspondingly.
* Space complexity : O(1) since it's a constant space solution.
*/
class Solution {
public boolean isMatch(String s, String p) {
if(p.isEmpty()) return s.isEmpty();
int sIndex = 0;
int pIndex = 0;
int starIndex = -1;
int siIndex = -1;
while(sIndex < s.length()) {
if(pIndex < p.length() &&
(p.charAt(pIndex) == '?' || s.charAt(sIndex) == p.charAt(pIndex))) {
sIndex++;
pIndex++;
} else if(pIndex < p.length() && p.charAt(pIndex) == '*') {
siIndex = sIndex;
starIndex = pIndex;
pIndex++;
} else if(starIndex != -1) {
sIndex = siIndex+1;
pIndex = starIndex+1;
siIndex++;
} else {
return false;
}
}
while(pIndex < p.length() && p.charAt(pIndex) == '*') {
pIndex++;
}
return pIndex == p.length();
}
}
Follow up
Count the Number of matching characters in a pair of strings - GFG
Last updated
Was this helpful?