正則表達(dá)式匹配

給定一個字符串?s?和一個字符規(guī)律?p，實(shí)現(xiàn)一個支持?'.'?和?'*'?的正則表達(dá)式匹配。

• '.'?匹配任意單個字符

• '*'?匹配零個或多個前面的那一個元素

'*'需要與前面一個字符綁定起來看，比如：

在 s 和 p 前面各插入一個空白字符‘ ’。

定義狀態(tài) dp[i][j] 表示字符串 s[0:i+1] 是否與正則表達(dá)式 p[0:j+1] 匹配，可以從3個過去的狀態(tài)得到?dp[i][j] 的值：

• dp[i][j-1]

• dp[i-1][j]

• dp[i-1][j-1]

考慮轉(zhuǎn)移條件即可。

編輯距離

給你兩個單詞 word1 和 word2， 請返回將?word1 轉(zhuǎn)換成 word2 所使用的最少操作數(shù)。可以對一個單詞進(jìn)行如下三種操作：

• 插入一個字符

• 刪除一個字符

• 替換一個字符

原理同上。