Leetcode Hard:写Regex

今天闲来无事,上Leetcode随便玩玩,结果这道hard题目做了一下午:

Given an input string s and a pattern p, implement regular expression matching with support for '.' and '*' where:

  • '.' Matches any single character.​​​​
  • '*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

一开始的思路是 :

(略)

这种思路的问题在于我们让a*尽可能多的匹配字符,所以不能通过例如 p = “a*a”, s = “aa” 这种测试。

于是我们发现需要iterate over 所有 a* 可能的数量。所以本题其实是一个regression,答案留给读者思考。

但是在例如p=“a*a*a*a*a*a*a*a*”这种case中无意义的搜索空间过大导致超时,可以预处理p合并所有连续的a*

最后可以使用dp来优化时间,方法如下:

(略)

Leave a Reply