题目描述

给定两个单词word1 和word2，计算出将word1转换成word2 所使用的最少操作数。你可以对一个单词进行如下三种操作：

插入一个字符

删除一个字符

替换一个字符

示例1:

示例2:

输入: word1 = “intention”, word2 = “execution”

输出: 5

解释:

intention -> inention (删除 ‘t’)

inention -> enention (将 ‘i’ 替换为 ‘e’)

enention -> exention (将 ‘n’ 替换为 ‘x’)

exention -> exection (将 ‘n’ 替换为 ‘c’)

exection -> execution (插入 ‘u’)

解题思路

我们通过两个指针i和j分别指向word1和word2。我们定义函数dp[i][j]表示word1[:i]转换为word2[:j]需要的最少步骤。

我们首先要比较word1[i]和word2[j]是不是相同，如果相同的话，我们就不用做任何操作，所以此时dp[i][j] = dp[i-1][j-1]（i和j都向前挪一个位置）。

接着对于不相同的时候我们的情况比较复杂，我们有三种处理手段，分别是insert、replace和remove。

insert操作 ，我们insert完之后，也就是word1中的元素会保持不变，而j会向前挪一个位置，也就是dp[i][j] = dp[i][j-1] + 1 。

replace操作 ，replace会减少word1和word2中一个需要比较的元素（i和j会向前挪一个位置），也就是dp[i][j] = dp[i-1][j-1]+ 1 。

remove操作 ，这个就很容易了，word1中会减少一个需要比较的元素，而我们j的位置不变，也就是dp[i][j] = dp[i-1][j]+1。所以我们最后的结果取三者取最小值即可。

动态规划算法为：

 dp[i][j] 代表 word1 的前i的字符 转成word2 前j个字符需要的步骤
1) 当word1[i] == word2[j]时
dp[i][j] = dp[i-1][j-1]
2) 当word1[i] != word2[j]时
dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1  

接着我们要考虑初始条件，也就是word1和word2为空的情况

 当i == 0 时 需要w1添加j个字符 才能变成w2 即 dp[0][j] = j
当j == 0 时 需要w1删除i个字符 才能变成w2 即 dp[j][0] = i  

代码示例

 func minDistance(word1 string, word2 string) int {
    l1 := len(word1)
  	l2 := len(word2)
	  dp := make([][]int, l1 + 1)
	  dp[0] = make([]int, l2 + 1)
	  for j := 0; j <= l2; j++{
		    dp[0][j] = j
	   }

	  for i := 1; i <= l1; i++{
		    dp[i] = make([]int, l2 + 1)
		    dp[i][0] = i
		    for j := 1; j <= l2; j++{
			      if word1[i-1: i] == word2[j-1:j]{
				        dp[i][j] = dp[i-1][j-1]
			      }else{
				        dp[i][j] = MinThree(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
		      	}
		    }
	   }
   	return dp[l1][l2]
}

func MinThree(a, b, c int) int {
	  var min int
	  if a >= b {
		    min = b
	  } else {
		    min = a
	 }
	if min >= c{
		   return c
	 }else{
		   return min
	 }
}