这题跟我原本预想的很不一样。我原来以为有点类似phone number 的regular matching。 原来是一个很像Edit Distance的题。
视频讲解的好： https://www.youtube.com/watch?v=DqhPJ8MzDKM
首先了解一下： .表示这个position可以为任何letter
*表示可以为0 or more of preceding elements.
主要基本可以分成2种情况。
跟Edit distance长得超像！ DP[i][j]表示用几个letter from S, 几个letter From P。 又是一个区间DP。
一个case： 最后letter matches， 那就看之前的match不match，所以是左上角。
一个case是： 如果P最后是*， 比如abcddd,和 abcd* 那么比较S的最后一个字母和P的*前面一个字母对不对先。对，ok，把S的除了最后一个字母和P的整个比较【包括*】。
*都是看2 letters before DP[i]的值决定。
理解完算法再写code就很简单了。
Regular Expression Matching
Implement regular expression matching with support for '....
Implement regular expression matching with support for '....
Implement regular expression matching with support for '....
Implement regular expression matching with support for '....
Implement regular expression matching with support for'.'...
Implement regular expression matching with support for '....
Implement regular expression matching with support for '....
10. Regular Expression Matching
10. Regular Expression Matching Implement regular express...
本文标题：Regular Expression Matching
本文链接：https://www.haomeiwen.com/subject/oxiilxtx.html
网友评论