题解 | #编辑距离(一)#
编辑距离(一)
https://www.nowcoder.com/practice/6a1483b5be1547b1acd7940f867be0da
package main /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param str1 string字符串 * @param str2 string字符串 * @return int整型 */ func editDistance(str1 string, str2 string) int { m, n := len(str1), len(str2) dp := make([][]int, m+1) for i := 0; i <= m; i++ { dp[i] = make([]int, n+1) } for i := 0; i <= m; i++ { dp[i][0] = i } for j := 0; j <= n; j++ { dp[0][j] = j } for i := 1; i <= m; i++ { for j := 1; j <= n; j++ { if str1[i-1] == str2[j-1] { dp[i][j] = dp[i-1][j-1] } else { dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) } } } return dp[m][n] } func min(a, b, c int) int { if a < b { if a < c { return a } return c } if b < c { return b } return c }