这题跟我原本预想的很不一样。我原来以为有点类似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就很简单了。
