search

soulmachine / leetcode

LeetCode题解，151道题完整版。
BSD 3-Clause "New" or "Revised" License
11.27k stars 3.43k forks source link

The solution of Regular Expression Matching is not O(N) #65

Open justmao945 opened 9 years ago

justmao945 commented 9 years ago

The recursive version can be accepted on leetcode, but it's not a O(N) solution. Please consider cases from wildcard matching:

abbabaaabbabbaababbabbbbbabbbabbbabaaaaababababbbabababaabbababaabbbbbbaaaabababbbaabbbbaabbbbababababbaabbaababaabbbababababbbbaaabbbbbabaaaabbababbbbaababaabbababbbbbababbbabaaaaaaaabbbbbaabaaababaaaabb
.*aa.*ba.*a.*bb.*aa.*ab.*a.*aaaaaa.*a.*aaaa.*bba

This case never return on my machine.