這題跟我原本預(yù)想的很不一樣毛仪。我原來(lái)以為有點(diǎn)類(lèi)似phone number 的regular matching波桩。 原來(lái)是一個(gè)很像Edit Distance的題。
視頻講解的好： https://www.youtube.com/watch?v=DqhPJ8MzDKM
首先了解一下： .表示這個(gè)position可以為任何letter
*表示可以為0 or more of preceding elements.?
主要基本可以分成2種情況永票。
跟Edit distance長(zhǎng)得超像扮宠！ DP[i][j]表示用幾個(gè)letter from S, 幾個(gè)letter From P抛虫。 又是一個(gè)區(qū)間DP松靡。
一個(gè)case： 最后letter matches， 那就看之前的match不match建椰，所以是左上角雕欺。
一個(gè)case是： 如果P最后是*， 比如abcddd,和 abcd* 那么比較S的最后一個(gè)字母和P的*前面一個(gè)字母對(duì)不對(duì)先棉姐。對(duì)屠列，ok，把S的除了最后一個(gè)字母和P的整個(gè)比較【包括*】伞矩。
*都是看2 letters before DP[i]的值決定笛洛。?
理解完算法再寫(xiě)code就很簡(jiǎn)單了。
