Wildcard Matching: LeetCode 44 Attempt 2

Question

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.

Answer 1

Move your code out of class Solution

I modified the method slightly.

If you no longer feel bound by the interface imposed on you by LeetCode, then I would not put your code inside a class at all. Instead, write a free function isMatch() that takes std::string_views as parameters. You can keep a stub class Solution that calls your code:

namespace {
    // Previously private functions can go into an anonymous namespace.
    …
}

bool isMatch(std::string_view text, std::string_view pattern) {
    …
}

class Solution {
public:
    bool isMatch(std::string s, std::string p) {
        return ::isMatch(s, p);
    }
};

Avoid one-letter variable names

The LeetCode question might have primed you to use short variable names, however this is bad practice. Use one-letter variable names only for very commonly used things, like i for a loop iterator.

Use .empty() consistently

You use .empty() in a few cases, but elsewhere you compare strings to "", or check that .size() is equal or unequal to zero. Use .empty() instead. While it doesn't matter much for std::string and std::string_view, there are other STL containers where .empty() might be much faster than any other method of checking if the container has any elements in it. It also unequivocally expresses your intent.

Make more use of std::string_view

splitWordsOut() still takes a reference to a std::string as a parameter. I would pass it a std::string_view instead. It also seems to me that it has to check for leading stars (because of begin != nullp[tr), and it's easy to tell if there is a trailing star (when split == true` after the loop). So maybe have it return both the words and whether there were leading and/or trailing stars?

struct SplitWordsResults {
    bool leadingStar;
    bool trailingStar;
    Words words;
};

SplitWordsResults splitWords(std::string_view pattern)
{
    SplitWordsResults results{};
    …
    return results;
}
…
bool isMatch(std::string_view text, std::string_view pattern)
{
    if (pattern.empty()) {
        return text.empty();
    }

    auto [leadingStar, trailingStar, words] = splitWords(pattern);
    …
}

Don't pass const references to std::string_views

Your function match() takes a const reference to a Word, which is the same as a std::string_view. That is rather redundant.

I think it's better not to declare the type aliases Word and Words. I don't think it saved any typing, and since it obscures the actual type, mistakes like this are easier to make.

Inadequate test suite

You only test a handful of combinations of texts and patterns, and this is by far not covering all the possible cases. I am missing empty patterns and texts, I am missing patterns that end with stars, I don't see any patterns with words that only consist of question marks, and so on.

While LeetCode probably throws a large variety of test cases at your program, don't trust that it will cover everything.

Further performance improvements

In splitWordsOut() you could reserve enough memory for result so it only ever needs to do one memory allocation:

result.reserve((pattern.size() + 1) / 2);

You can also be smarter when match() fails. Consider that if you have a text like:

aaaaabaaaaac

And you have a pattern:

*aaaaac*

Then when match() is called with pos = 0, it will start comparing the start of the text with the word of the pattern. This all goes well until it sees the b, then it fails. You then try again with pos = 1, but at this point you actually know that this will fail to match as well. Instead, you can skip immediately to pos = 5, at least with this pattern, since b is not a character that matches anything in the pattern. If you replace the b with an a in the text, then you could not skip that much, because maybe the c would have been right after where the b was.

Given the pattern you can build a finite state automaton that will try to match the text against the pattern, and such that when it finds a mismatch, it knows exactly how much of the text it can skip. This is actually a large part of what std::regex() does. I already explained earlier that this could actually be bad for performance. However, there might be a middle ground where you have a few simple heuristics that are cheap to implement but can greatly speed up some of the cases. Since you already beat 100% of the other LeetCode entries, that might not be worth pursuing though.