[Day9]-[动态规划] 编辑距离

输入：word1 = "horse", word2 = "ros"输出：3解释：horse -> rorse (将 'h' 替换为 'r')rorse -> rose (删除 'r')rose -> ros (删除 'e')

输入：word1 = "intention", word2 = "execution"输出：5解释：intention -> inention (删除 't')inention -> enention (将 'i' 替换为 'e')enention -> exention (将 'n' 替换为 'x')exention -> exection (将 'n' 替换为 'c')exection -> execution (插入 'u')

func minDistance(word1 string, word2 string) int {	var min func(x, y int) int           // 最小值	var solution func(s1, s2 string) int // 解决方案	min = func(x, y int) int {		if x < y {			return x		}
		return y	}
	solution = func(s1, s2 string) int {		m, n := len(s1), len(s2)    // 两个字符串的长度		var dp = make([][]int, m+1) // dpTable dp[0][i] 和 dp[j][0] 为基态数据		for i := 0; i <= m; i++ {			dp[i] = make([]int, n+1) // 初始化二维数据带零值			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 s1[i-1] == s2[j-1] { // 从字符串的第1个字符开始比较					dp[i][j] = dp[i-1][j-1] // 如果相等 编辑距离不变				} else {					// 取插入，删除，替换 的最小距离+1					dp[i][j] = min(dp[i][j-1]+1, min(dp[i-1][j]+1, dp[i-1][j-1]+1))				}			}		}
		// 终态就是 两个字符串都分析完了		return dp[m][n]	}
    return solution(word1,word2)}