一、题目
1、算法题目
“给定两个单词，计算出单词1转换为单词2所最少操作数。”
题目链接：
来源：力扣（LeetCode）
链接：72. 编辑距离 - 力扣（LeetCode） (leetcode-cn.com)
2、题目描述
给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
- 插入一个字符
- 删除一个字符
- 替换一个字符
示例 1： 输入：word1 = "horse", word2 = "ros" 输出：3 解释： horse -> rorse (将 'h' 替换为 'r') rorse -> rose (删除 'r') rose -> ros (删除 'e') 复制代码
示例 2： 输入：word1 = "intention", word2 = "execution" 输出：5 解释： intention -> inention (删除 't') inention -> enention (将 'i' 替换为 'e') enention -> exention (将 'n' 替换为 'x') exention -> exection (将 'n' 替换为 'c') exection -> execution (插入 'u') 复制代码
二、解题
1、思路分析
找出所有解，可以用动态规划。
对于任意一个单词进行插入删除替换操作，转换成第二个单词即可。
2、代码实现
代码参考：
public class Solution { public int MinDistance(string w1, string w2) { //【dp数组定义】w1转为w2所需的最小操作数 int[,] dp = new int[w1.Length + 1, w2.Length + 1]; //【初始化】 for (int i = 0; i <= w1.Length; i++) dp[i, 0] = i; for (int j = 0; j <= w2.Length; j++) dp[0, j] = j; //【状态转移】 for (int i = 1; i <= w1.Length; i++) { for (int j = 1; j <= w2.Length; j++) { if (w1[i - 1] == w2[j - 1]) //如果最后一位相等，最少操作数无影响 dp[i, j] = dp[i - 1, j - 1]; else //如果不相等，到d[i,j]一共有3种状态，取最小：替换、w1新增w2的最后1位、w2新增w1的最后1位 dp[i, j] = Math.Min(dp[i - 1, j - 1], Math.Min(dp[i - 1, j], dp[i, j - 1])) + 1; } } return dp[w1.Length, w2.Length]; } } 复制代码
网络异常，图片无法展示
|
3、时间复杂度
时间复杂度 ： O(n)
其中n是数组的长度，只需要遍历一遍数组即可求得答案。
空间复杂度： O(1)
只需要常数级别的空间存放变量。
三、总结
1.选择什么套路来做？题目是序列的处理问题，一般带有“最少”“最多”“最大”“子序列”等可以一步步解决的字符串或数组问题，可以考虑用DP，2个序列的比较，用dp[i,j]二维数组；
2.再想DP数组的含义是什么，一般就是按问题描述，比如本题dp[i,i]就是将长度为i的word1 转换成长度为j的word2 所使用的最少操作数；
3.既然使用了dp[i,j]，就要想这种状态是怎么得来的，即状态转移方程，就要分情况了，一般是先比较两个序列的最后1位，是否相等，针对本题：
如果最后1位相等：则删除或新增这1位，对最少操作数没有影响，即dp[i,j] = dp[i-1,j-1];
如果最后1位不相等，如何让它们相等？有下面这几种情况：
- Ⅰ：替换最后1位，无论替换哪个操作数都是1：dp[i,j] = dp[i-1,j-1]+1；
- Ⅱ：第1个数组新增1位，使最后1位与第2个数组的最后1位相等：dp[i,j] = dp[i-1,j]+1；
- Ⅲ：第2个数组新增1位，使最后1位于第1个数组的最后1位相等：dp[i,j] = dp[i,j-1]+1；
同时，时刻想清楚dp[i,j]、dp[i-1,j-1]、dp[i-1,j-1]、dp[i,j-1]的含义即可。
