这两道题第一眼看上去都差不多,通常思路就是用动态规划做。
对于Regular Expression Matching可以50ms通过所有test case;
而对于Wildcard Matching却需要900ms.
不知道OJ用了什么不同的test case,但是DP的时间复杂度是M*N的,没道理差别这么大。Dissuss里很多人用DP还不能通过。
原因可能如下:
bool OPT[m+1][n+1]
size of the mentioned test case : s.size()= 32316, p.size(): 32318
This means a memory location of 32317*32319 bytes is required which is way past the maximum limit allowed for continuous memory allocation with an array structure.
看了Accepted Solution Runtime Distribution后,才发现Wildcard Matching有“线性”做法,就是Yu的做法:
http://yucoding.blogspot.com/2013/02/leetcode-question-123-wildcard-matching.html
但是Yu的算法worst case running time 也是M*N的。