3
\$\begingroup\$

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.

\$\endgroup\$
0

1 Answer 1

1
\$\begingroup\$

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.

\$\endgroup\$
5
  • \$\begingroup\$ Thanks. Agree with all that (I am changing the code). What is the name of this construct? auto [leadingStar, trailingStar, words] = splitWords(pattern);. Unit tests are based on the tests that failed in LeetCode and I was trying to test offline :-) \$\endgroup\$ Feb 14 at 23:42
  • \$\begingroup\$ It's called a structured binding, it was introduced in C++17. \$\endgroup\$
    – G. Sliepen
    Feb 15 at 8:34
  • \$\begingroup\$ I changed the structure SplitWordsResults into a std::tuple<bool, bool, Words> as the return type. Then return {leadingStar, trailingStar, regExpWords} then used the structure binding to unpack it at the call site. \$\endgroup\$ Feb 15 at 15:22
  • \$\begingroup\$ I would avoid using std::tuple if you can make a struct just as easily. The advantage of a struct is that you can give it and its members names, so it's much more self-documenting than a std::tuple is. You can still use the statement return {leadingStar, trailingStar, regExpWords} even if the return type is a struct. \$\endgroup\$
    – G. Sliepen
    Feb 15 at 16:12
  • \$\begingroup\$ Interesting argument for not using tuple. I can definitely see the self documenting part. Going to have to think about that. \$\endgroup\$ Feb 16 at 3:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.