Leetcode 44: Wildcard Matching

There were some tricky test cases in this problem that meant my original recursive solution was too slow. My second attempt 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:

This entry was posted in programming and tagged , , . Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *