Follow up post
Link to question:
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).
Note:
The framework provides the class Solution and the method bool isMatch(string s, string p) where you are supposed to implement the solution. I modified the method slightly.
class Solution
{
// Check if there is a match between input s and matching char p.
// Note '?' matches any character:
bool check(char s, char p) {
return (p == '?') || (s == p);
}
// Check for match on star.
// s: Input String
// sPos: position in input string.
// p: match expression.
// pPos: position in match expression.
// max: The maximum number of normal characters we need to match against.
// This is used to limit the potential length of characters that a
// star can match against (as we need at least that many characters
// left to match normal characters.
bool starMatch(string const& s, int sPos, string const& p,int pPos, int max)
{
// Max length in s we can match against.
int maxLen = s.size() - sPos - max;
for (int loop = 0; loop <= maxLen; ++loop) {
if (tryMatch(s, sPos + loop, p, pPos + 1, max)) {
return true;
}
}
// No matter what size of match we used we did not find
// a match to the following part of p.
return false;
}
// Do the actual work of matching.
bool tryMatch(string const& s, int sPos, string const& p,int pPos, int max)
{
while (sPos < s.size() && pPos < p.size()) {
if (p[pPos] == '*') {
// A star forces a recursive call that will do sub matches
// so we can exit.
return starMatch(s, sPos, p, pPos, max);
}
// Otherwise do a single character match.
if (!check(s[sPos], p[pPos])) {
return false;
}
++sPos;
++pPos;
--max;
}
// We can run out of characters in s
// But the p expression can still be a `*` as that can match with
// zero characters.
if (pPos < p.size() && p[pPos] == '*') {
++pPos;
}
return sPos == s.size() && pPos == p.size();
}
public:
// Start point
bool isMatch(string const& s, string const& p)
{
std::string save;
//save.resereve(s.size());
// Count the maxnumber of normal characters we can match against.
// Also remove consecutive '*' as that is meaningless.
int max = 0;
bool lastStar = false;
for (char x: p) {
if (x != '*') {
++max;
save.append(1, x);
lastStar = false;
}
else if (!lastStar) {
save.append(1, x);
lastStar = true;
}
}
// Now try and do the match.
return tryMatch(s, 0, save, 0, max);
}
};
The code works. Problem it exceeds the time limit on one of the test cases.
s =
"abbabaaabbabbaababbabbbbbabbbabbbabaaaaababababbbabababaabbababaabbbbbbaaaabababbbaabbbbaabbbbababababbaabbaababaabbbababababbbbaaabbbbbabaaaabbababbbbaababaabbababbbbbababbbabaaaaaaaabbbbbaabaaababaaaabb"
p =
"**aa*****ba*a*bb**aa*ab****a*aaaaaa***a*aaaa**bbabb*b*b**aaaaaaaaa*a********ba*bbb***a*ba*bb*bb**a*b*bb"
I tried to cheat with:
class Solution {
public:
bool isMatch(string const& s, string const& p) {
std::string reg;
reg.append("^");
bool seenStar = false;
for (auto const& c: p) {
if (c == '?') {
reg.append(".");
seenStar = false;
}
else if (c == '*') {
if (!seenStar) {
reg.append(".*");
}
seenStar = true;
}
else {
reg.append(1, c);
seenStar = false;
}
}
reg.append("$");
return std::regex_match(s, std::regex(reg));
}
};
But this also exceeds the time limit.
I tried to work out how to use a FSM with a state table but could not work out how to represent *.
