The obvious solution is to use a recursive function. If we find a wildcard then we recurse every position in s from that point onwards. The problem with this is that it is very slow if there are a lot of wildcards and some of the leetcode test cases will fail. So we need to add DP memoization to eliminate duplicate branches of recursive calls.
I also have a different solution that was inspired by this post:
http://yucoding.blogspot.com/2013/02/leetcode-question-123-wildcard-matching.html
The solution basically steps through matches and then if it finds a * wildcard pattern character then it stores its positions in the pattern and string. It then attempts to just step past the wildcard and if at some point it fails then it rewinds back to the original position but skips forward one position in the string. So it tests out further matches by using an increasing number of characters used by the wildcard.
Here are my whiteboard notes where I try to explain the logic. Note that I use the cs and cp variables as the indexes of the current positions in the pattern and string. However at the top of the whiteboard I started out using “is” and “ip” instead of cs and cp. I also use sp for the star position in the pattern and ss for the position of the star matching in the string.
I think this has a worst case time complexity of O(n²). I think it might be possible to use the KMP algorithm to achieve O(n) but that is quite a bit more complicated. I think this solution is far more elegant. Here is the c++ source code: