4
\$\begingroup\$

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 *.

\$\endgroup\$

2 Answers 2

3
\$\begingroup\$

Nice code, good identifiers.


            if (tryMatch(s, sPos + loop, p, pPos + 1, max)) {

In starMatch, don't we maybe get to reduce max ?

            if (tryMatch(s, sPos + loop, p, pPos + 1, max - loop)) {

When I look at

p = "*aa*ba*a*bb*aa*ab*a*aaaaaa*a*aaaa*bbabb*b*b*aa?aaaaaa*a*ba*...bb"

I see a vector of words: ["aa", "ba", "a", "bb", "aa", "ab", "a", "aa?aaa", ...]

Here are some ways to exploit that. We wish to find anchors.

  1. For each word, scan s to count occurrences of the word. If count is exactly one then word is an unambiguous anchor. Use that to partition into a pair of smaller subproblems.
  2. For each word, to treat it as a candidate anchor, compute a list of the word's candidate starting indexes, and find the length of that list. Order words by that length. Use that to drive down the combinatorics.
  3. Similar to (2.) but without the concept of a "word". Find the s alphabet and let its size be S. Compute n-grams for both s and p, preserving the input offset. If a p word contains a ?, then emit S entries for it, permitting any possible match. Order both the p and the s lists of n-grams by frequency. Now start treating n-grams as candidate anchors and let a mergesort of the lists drive the combinatorics.

It feels like the n-gram indexes should induce a partial ordering, and then we could topo sort the poset. Sorry; not seeing how to get there.

\$\endgroup\$
2
  • \$\begingroup\$ In starMatch, don't we maybe get to reduce max ? No. This is because max is the number of none special characters in "p" that still have to be matched with letters in "s". \$\endgroup\$ Commented Feb 13, 2023 at 23:06
  • \$\begingroup\$ Thanks: codereview.stackexchange.com/q/283296/507 \$\endgroup\$ Commented Feb 14, 2023 at 18:27
2
\$\begingroup\$

Make sure you match the required API

Ideally, you wouldn't use a class Solution for this, and just create free functions. However, if you are given an API you have to follow, make sure you match it exactly. Your version of isMatch() takes references to const strings, but the LeetCode question gives you a prototype that takes references to mutable strings.

That said, if you didn't have LeetCode's restrictions, taking them by const reference is preferrable, although since C++17 it is even better to use std::string_view parameters.

Why std::regex() exceeds the time limit

The problem is that std::regex() has to compile a data structure that is suitable for std::regex_match() to match the string against. Once you have that data structure, it is probably very fast, but this extra compilation stage, which can only be done at runtime, will add significant overhead.

Note that if you want to cheat, you might have better luck trying to use the POSIX fnmatch() function.

Avoid scanning the pattern twice

You first scan the pattern to remove redundant '*'s. However, you could easily do that in tryMatch(): if you encounter a '*', check if the next character is one as well, if so increment pPos until you find a different character.

Avoid exponential recursion

tryMatch() and starMatch() call each other inside loops. This quickly can lead to an explosion of recursion. Ideally, you want to find a way that avoids this and is as close to a linear scan of the input as possible.

As J_H mentioned in his post, split the pattern on the stars, so you are left with a vector of words. Search for the earliest occurence of the first word, then check for the earliest occurence of the second word that comes after the first word, and so on. If you found all the words, you are mostly done, you only need to account for stars at the start and end of the pattern.

You don't need to find all occurences of a given word, the first occurence is enough.

\$\endgroup\$
4
  • \$\begingroup\$ "You don't need to find all occurences of a given word, the first occurence is enough." Ooohh! That's really interesting, if true. But with all due respect, I don't believe it is. I mean, the adversary gets to be arbitrarily annoying, right? So we could have p = "*aaaa*aaaa*aaaa*aaaabaaaa*aaaa*aaaa*aaaa*", and worse, some of those words could have ? within them. :-p But maybe even first match helps with the exponential explosion. \$\endgroup\$
    – J_H
    Commented Feb 13, 2023 at 19:54
  • \$\begingroup\$ @J_H Think of it this way: the first word needs to come before the other words. So the earlier you find the match, the more remains of the input string that the rest of the pattern can be matched against. Of course, if there is no star after the last word, you need to treat the last word differently: it has to match exactly the end of the input string. But that's still trivial to do. \$\endgroup\$
    – G. Sliepen
    Commented Feb 13, 2023 at 20:53
  • \$\begingroup\$ Right! And that's something I'd really like to exploit. But in the example *aaaa*aaaa*aaaa* I have trouble distinguishing "this word before that word" since they all look alike, and the * could be matching a bunch of a's. And it's worse for a word containing one or more ?'s. \$\endgroup\$
    – J_H
    Commented Feb 14, 2023 at 0:23
  • \$\begingroup\$ @J_H Consider this argument: suppose you have a pattern and a matching string. You have the position of each word of the pattern in the matching string. Now suppose you find an earlier match for the first word in the string. You can freely move the first word to that earlier position, since the * after the first word in the pattern will cover all the extra characters that are now between the position of the first word and the second word. You can repeat this until the first word is at the earliest possible position. Then you can do the same for the second word, and so on. \$\endgroup\$
    – G. Sliepen
    Commented Feb 14, 2023 at 8:29

Your Answer

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

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