Two explained points in the highest voted solution

  • 0

    The highest voted solution is based on:

    If it is not very obvious for you, I will try to explain the following two reasons why it works:

    1. Greedy matching works, there is no need to backtrack more than once.

    Obviously, we need to use backtrack, but why Yu's solution didn't use a stack? The reason is, we only need to backtrack once to go back to the most recent '*'. Let me explain why. Given a string s and a pattern p, Consider the pattern string is divided into two substrings, p1 and p2, each of which starts with a '*'. With greedy matching, which is the case in Yu's solution, suppose p1 matches the shortest head substring of s, namely s1. Let's name its complement as s2, then we have s = s1 + s2 and p = p1+p2.

    The statement is:
    If p2 doesn't match s2 then p doesn't match s.

    The proof is the following:
    If s1 is the only head substring of s matching p1, then we don't have alternative matches for p1, then the only case is checked.
    If there is another head substring of s matching p1, namely s1' which must be longer than s1, then its complement, name s2' must be a tail substring of s2. We know that p2 doesn't match s2, and p2 starts with '*', then we know p2 doesn't match any tail substring of s2, so p2 doesn't match s2' either. To illustrate, consider:

    • p2 = "*z"
    • s2 = "abcd"

    p2 doesn't match s2, and p2 doesn't match any of "bcd", "cd", or "d". This is because in eyes of '*' "abc" "bc" "c" and "" are all the same.

    2. C string all ends with a null char '\0'.
    This actually makes his problem easier to solve with C string, and if the inputs are std::string, the best way to do it is to use their c_str() to solve it.

    The convenience is that when the pointer of pattern string p is at the end, pointing to '\0', matching attempt with any char of string s (not including its end '\0') will result in failure. This is equivalent to the following behavior:

    When characters in pattern string p are all matched but there are still characters remaining in string s, this matching attempt is a failure.

    If such logic is implemented in std::string, we need to use either the size of string or its end iterator.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.