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.