Leetcode 44: wildcard matching

June 17, 2017

Problem statement

It is hard level algorithm. Julia tried the algorithm a few times in mocking experience, she used the algorithm a few time to interview and also was interviewed.

Now it is 9:36 am, Julia likes to read some discussion. Plan to spend 20 - 30 minutes.

First, Julia was advised in mocking experience to use recursive function to make the code more easy to write.

Special test cases are looked into:

1. ?*, any character repeated multiple time, ? represents any character, * means repeating multiple times.

2. If string is finished, but the pattern string is not, it is still possible to match. Pattern string ?*, a* or a*b* etc.

3. Some challenging matching, like "aaa" to match "a*a", how to wisely calculate a* pattern to match first two chars instead of all three characters.

Study code using DP solution - link is here.