Original post:
Based on feedback from J-H in his answer I have done another attempt.
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.
#include <vector>
#include <string>
#include <string_view>
class Solution {
using Word = std::string_view;
using Words = std::vector<Word>;
// Check a single character match.
bool check(char p, char s)
{
return p == '?' || p == s;
}
// Try and match "word" to text starting at point pos.
bool match(Word const& word, std::string_view text, std::size_t pos)
{
text.remove_prefix(std::min(pos, text.size()));
return text.size() >= word.size() && std::equal(std::begin(word), std::end(word), std::begin(text), [&](auto p, auto s){return check(p,s);});
}
// Match a list of "words" against the text in order.
// Each word may be have a prefix in text that is ignored.
// Note:
// Remove the matched text from the input "text"
// Return true if all words matched.
bool matchWords(Words const& words, std::string_view& text)
{
std::size_t word = 0;
std::size_t loop = 0;
for (; loop < text.size() && word < words.size(); ++loop) {
if (match(words[word], text, loop)) {
loop += words[word].size() - 1;
++word;
}
}
text.remove_prefix(std::min(loop, text.size()));
return word == words.size();
}
// Split the text into a list of words separated by '*'
Words splitWordsOut(std::string const& p)
{
Words result;
char const* begin = nullptr;
char const* end = nullptr;
bool split = true;
for (auto& c: p) {
if (c == '*') {
split = true;
}
else {
if (split) {
if (begin != nullptr) {
result.emplace_back(begin, std::distance(begin, end));
}
begin = &c;
end = begin;
}
++end;
split = false;
}
}
if (begin != nullptr) {
result.emplace_back(begin, std::distance(begin, end));
}
return result;
}
public:
bool isMatch(std::string const& s, std::string const& p)
{
// Trivial test.
// By doing this test here we don't need to check for empty string in other checks.
if (p == "") {
return s == "";
}
// Check for leading and trailing stars.
bool leadingStar = p.front() == '*';
bool trailingStar = p.back() == '*';
std::string_view text(s);
Words words = splitWordsOut(p);
// If there is not a trailing star the expression is anchored to the end of the string
// So we need to test the last word matches the exact end of the string.
if (!trailingStar && words.size() != 0) {
if (!match(words.back(), text, text.size() - words.back().size())) {
return false;
}
text.remove_suffix(words.back().size());
words.pop_back();
}
// If the last character is not a star we have already tested and removed it.
// This means the in the final matching we can match any unmatched text automatically
// unless there is only one word not prefixed by a star.
// See: the final return on how this is used.
bool lastStar = words.size() != 0 || leadingStar;
// If the first word is not prefixed by start then the first word is anchored to
// the beginning. So see if we can match it.
if (!leadingStar && words.size() != 0) {
if (!match(words.front(), text, 0)) {
return false;
}
text.remove_prefix(words.front().size());
words.erase(words.begin());
}
// At this point all words have a star prefix.
// So when doing matches we can ignore any leading characters that don't match.
// So now we just need to see if we can find each word in the text in order.
return matchWords(words, text) && (text.empty() || lastStar);
}
};
Test Harness:
#include <iostream>
int main()
{
Solution s;
std::cout << "Result: 1 == " << s.isMatch("aa", "aa") << "\n\n\n\n";
std::cout << "Result: 1 == " << s.isMatch("adceb", "*a*b") << "\n\n\n\n";
std::cout << "Result: 0 == " << s.isMatch("mississippi", "m??*ss*?i*pi") << "\n\n\n\n";
std::cout << "Result: 1 == " << s.isMatch("aaaa", "***a") << "\n\n\n\n";
}
Running it a few times.
Got runtimes of usually 6 -> 9 ms range.
Best runtime was 0ms (got a lucky run on a non busy machine) Beating 100% of the other entries. Has memory usage of 6.6MB, beating 96.51% of entries in Memory usage.