题解 | #编辑距离(一)#

package main

/*
*
给定两个字符串 str1 和 str2 ，请你算出将 str1 转为 str2 的最少操作数。
你可以对字符串进行3种操作：
1.插入一个字符
2.删除一个字符
3.修改一个字符。
*/
func editDistance(str1 string, str2 string) int {
	n := len(str1)
	m := len(str2)
	dp := make([][]int, n+1)
	for i := 0; i <= n; i++ {
		dp[i] = make([]int, m+1)
	}
	for i := 0; i <= n; i++ {
		for j := 0; j <= m; j++ {
			if i == 0 && j > 0 {
				dp[i][j] = dp[i][j-1] + 1
			} else if i > 0 && j == 0 {
				dp[i][j] = dp[i-1][j] + 1
			} else if i > 0 && j > 0 {
				dp[i][j] = dp[i-1][j] + 1
				if dp[i][j-1]+1 < dp[i][j] {
					dp[i][j] = dp[i][j-1] + 1
				}
				val := dp[i-1][j-1]
				if str1[i-1] != str2[j-1] {
					val++
				}
				if val < dp[i][j] {
					dp[i][j] = val
				}
			} else {
				dp[i][j] = 0
			}
		}
	}
	return dp[n][m]
	// write code here
}