经典dp--字符串系列之Go写法

经典dp--字符串系列之Go写法

[Edit Distance](https://leetcode.com/problems/edit-distance/)[Longest Common Subsequence](https://leetcode.com/problems/longest-common-subsequence/)[剑指 Offer 19. 正则表达式匹配](https://leetcode-cn.com/problems/zheng-ze-biao-da-shi-pi-pei-lcof/)[44. 通配符匹配](https://leetcode-cn.com/problems/wildcard-matching/) 在这里我目前碰到了一些的字符串dp处理的问题，这些问题结构很相似，都是借助二维数组来保存状态，根据这种状态来转移更新。其中1、2是一组题，3、4是一组题

PS：画个矩阵出来比一比更加形象生动！！！

Edit Distance

编辑距离这道题连接和题目描述见原链接（标题）

首先，我们定义一个dp数组，大小为m = len(word1), n = len(word2)。dp[i][j]的含义表示子串word1[0:i]和word2[0:j]的最小编辑距离。

然后，我们可知操作主要有四种，也就是插入、删除、替换和什么都不搞，这四种操作我们可以看做获得最优解的一个状态，也就是说我们当前状态是通过这四种操作而获得。

所以我们有情况，当word1[i] == word2[j]时，dp[i][j]= dp[i-1][j-1], 因为两个相等了，就不需要操作了；当word1[i] != word2[j]时, 这是我们有三种操作可以选择，当然，我们求最小编辑距离，就是从三种操作中选择最小的那个：min(dp[i-1][j], dp[i][j-1],dp[i-1][j-1]) + 1

dp[i][j] = dp[i-1][j-1]      ,if word1[i] == word2[j] dp[i][j] = minValues(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) + 1   , otherwise

在这里特别说明一下dp[i][j-1]表示对word1进行插入，dp[i-1][j]表示对word1进行删除，dp[i-1][j-1]表示对word1进行替换

最后，我们需要明确一下边界，也就是初始值，我们需要对dp数组进行初始化，也就是dp数组大小是(m+1) x (n+1)的，初始化的值为对应的长度。举个简单的例子就是，假定word2长度为0，对于子串word1[0:i]对应的初始值dp[0][i] = i, 因为这个匹配是要不断删除word1字母，同理dp[i][0] = i

func minDistance(word1 string, word2 string) int { len1 := len(word1) len2 := len(word2) dp := make([][]int, len1+1) for i:=0; i<=len1; i++ { dp[i] = make([]int, len2+1) } // init 边界 for i:=1; i<=len2; i++ { dp[0][i] = i } for i:=1; i<=len1; i++ { dp[i][0] = i } // finish init for i:=1; i<=len1; i++ { for j:=1; j<=len2;j++ { // 根据状态转移方程计算dp[i][j] if word1[i-1] == word2[j-1] { dp[i][j] = dp[i-1][j-1] } else { dp[i][j] = minValues(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) + 1 } } } return dp[len1][len2] } func minValues(values ...int) int { res := math.MaxInt32 for _, v := range values { if v < res { res = v } } return res }

Longest Common Subsequence

有了上面那个例子的，我们这个题也是相对比较类似的

首先，我们定义一个dp数组，大小为m = len(text1), n = len(text2)。dp[i][j]表示子串text1[0:i]和text2[0:j]的之间最大的公共子序列（LCS）。

然后我们需要确定状态，在这里状态有三种，当text1[i] == text2[j]时，我们的LCS比dp[i-1][j-1]要长一个单位；当text1[i] != text2[j]时, 我们可以根据dp[i-1][j]或者 dp[i][j-1]这两个状态中选一个最大的作为我们的值：

dp[i][j] = 1 + dp[i-1][j-1]      ,if text1[i] == text2[j] dp[i][j] = max(dp[i-1][j], dp[i][j-1])    ,if text1[i] != text2[j] **边界问题**则相对来说比较简单，某个`text`为空，其`dp`数组都为`0`，因为没有LCS。 func longestCommonSubsequence(text1 string, text2 string) int { len1 := len(text1) len2 := len(text2) dp := make([][]int, len1 + 1) for i:=0; i<=len1; i++ { dp[i] = make([]int, len2+1) } //finish init for i:=1; i<=len1; i++ { for j :=1; j<=len2;j++ { // 根据状态转移方程计算dp[i][j] if text2[j-1] == text1[i-1] { dp[i][j] = 1 + dp[i-1][j-1] } else { dp[i][j] = max(dp[i-1][j], dp[i][j-1]) } } } return dp[len1][len2] } func max(a, b int) int { if a < b { return b } return a } PS 还是那句话，自个画个矩阵图来体会一下效果更加好

剑指 Offer 19. 正则表达式匹配

同时，这里需要考虑了到三种字符串匹配模式：1. 正常字符；2. ?字符；3. *字符。其中 *字符对其前面的字符出现次数又分为三种情况：0次，1次和多次。针对这几种情况，我们对应获得其状态转移方程：(这里定义了一个 m + 1 x n + 1大小的dp矩阵(m = len(s), n = len(p))，因此j - 1 表示当前p指向的字符)

状态转移方程：

当 p[j - 1] != '*'时，dp[i][j] == true的前提是dp[i - 1][j - 1] == true，这是确保前面字符串能匹配上，如果不能匹配，后面就是全都匹配上也没有用了。在dp[i - 1][j - 1] == true前提下，dp[i][j] == true成立只有s[i-1] == p[j - 1] 或者p[j - 1] == '.'。

当 p[j - 1] == '*'时，有三种情况：

0次，这里就相当于去掉了p[j-1:j]字符串，因此这里我们可以用dp[i][j-2]来表示

1次，这里就是相当于p[j-1]不存在，因此这里我们可以用dp[i][j-1]来表示

多次，这种情况dp[i][j] == true的前提是dp[i - 1][j] == true，这里是保证了p[j]与s[:i-1]要匹配上，也就是当前'*'的前面字符取一次的情况是否匹配上。只有在匹配上才进行下一步考虑。因此在dp[i - 1][j] == true前提下，dp[i][j] == true成立只有s[i-1] == p[j - 2] 或者p[j - 2] == '.' （这里就是取当前'*'的前面字符是否匹配上当前s[i-1]）

边界条件为：

s，p都为空时候为真：dp[0][0] = trues不为空，p为空：dp[i][0] = falses为空，p不为空：只有偶数位的字符都为*时为真，比如说"u*9*"，所以有dp[0][j] = dp[0][j - 2] && p[j - 1] == '*'

所以有对应的代码：

func isMatch(s string, p string) bool { m, n := len(s), len(p) dp := make([][]bool, m + 1) for i := 0; i < m + 1; i++ { dp[i] = make([]bool, n + 1) } dp[0][0] = true for j := 2; j < n+1; j += 2 { // 边界条件 dp[0][j] = dp[0][j - 2] && p[j - 1] == '*' } for i := 1; i <= m; i++ { for j := 1; j <= n; j++ { if p[j -1] != '*' { if dp[i - 1][j - 1] { // 转移状态1 dp[i][j] = s[i - 1] == p[j - 1] || p[j - 1] == '.' } } else { // 转移状态2 dp[i][j] = dp[i][j - 2] || dp[i][j - 1] // 0次或者1次 if dp[i - 1][j] { // 多次 dp[i][j] = dp[i][j] || s[i - 1] == p[j - 2] || p[j - 2] == '.' } } } } return dp[m][n] }

44. 通配符匹配

这个题跟上面的题很像，思路大致都是一样的，不同的是状态转移方程和边界条件的区别而已（题目都不一样当然不同了），这里的区别就是*可以匹配任何东西，而且跟前面字符完全无关了，?匹配任何单个字符。

因此这里按照上面的思路，也是分为两种情况。

状态转移方程：

当 p[j - 1] != '*'时，dp[i][j] == true的前提是dp[i - 1][j - 1] == true，这是确保前面字符串能匹配上，如果不能匹配，后面就是全都匹配上也没有用了。在dp[i - 1][j - 1] == true前提下，dp[i][j] == true成立只有s[i-1] == p[j - 1] 或者p[j - 1] == '?'。当 p[j - 1] != '*'时, 这题只有两种情况了： 不匹配任何字符（空字符），可用dp[i][j-1] 表示匹配任何字符，可用dp[i - 1][j] 表示

边界条件为：

s，p都为空时候为真：dp[0][0] = true

s不为空，p为空：dp[i][0] = false

s为空，p不为空：只有当前p[j - 1] == '*'并且前面的字符串能匹配上才是为真，也就是dp[0][j] = dp[0][j-1] && p[i-1] == '*'

因此有代码：

func isMatch(s string, p string) bool { m, n := len(s), len(p) dp := make([][]bool, m + 1) for i := 0; i <= m; i++ { dp[i] = make([]bool, n + 1) } dp[0][0] = true for j := 1; j <= n; j++ { // 边界条件 dp[0][j] = dp[0][j-1] && p[j-1] == '*' } for i := 1; i <= m; i++ { for j := 1; j <= n; j++ { if p[j-1] != '*' { // 转移状态1 if dp[i - 1][j - 1] { dp[i][j] = p[j - 1] == s[i - 1] || p[j - 1] == '?' } } else { // 转移状态2 dp[i][j] = dp[i-1][j] || dp[i][j-1] } } } return dp[m][n] } // 矩阵反过来的形式也是可以的，初始化就可以不用单独一个for循环了 func isMatch(s string, p string) bool { m, n := len(p), len(s) dp := make([][]bool, m + 1) for i := 0; i <= m; i++ { dp[i] = make([]bool, n + 1) } dp[0][0] = true for i := 1; i <= m; i++ { dp[i][0] = dp[i-1][0] && p[i-1] == '*' // 边界条件 for j := 1; j <= n; j++ { if p[i-1] == '*' { // 转移状态2 dp[i][j] = dp[i-1][j] || dp[i][j-1] } else { // 转移状态1 if dp[i - 1][j - 1] { dp[i][j] = p[i - 1] == s[j - 1] || p[i - 1] == '?' } } } } return dp[m][n] }