简单的静态网页代码,搜索引擎优化工作原理的先后顺序,专业的网站建设公司哪家好,余姚本地网站排名题目
72. 编辑距离
中等
相关标签
字符串 动态规划
给你两个单词 word1 和 word2#xff0c; 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作#xff1a;
插入一个字符删除一个字符替换一个字符 示例 1#xff1a;
输入 请返回将 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)提示
0 word1.length, word2.length 500word1 和 word2 由小写英文字母组成
思路和解题方法 具体来说对于给定的两个字符串 word1 和 word2首先创建一个二维数组 dp 来保存它们之间的编辑距离。然后分别初始化数组的第一行和第一列使得 dp[i][0] i 和 dp[0][j] j其中 i 和 j 分别表示字符串 word1 和 word2 的长度。这样初始化是为了表示将 word1 和空串或者将 word2 和空串进行匹配时的编辑距离。 接下来从第二行和第二列开始对于每个位置 (i,j)先判断 word1 和 word2 在当前位置上的字符是否相同。如果相同则说明不需要进行任何编辑操作因此 dp[i][j] 可以直接继承上一个位置的编辑距离即 dp[i-1][j-1]。否则需要在上一个位置的编辑距离的基础上增加一些编辑操作例如插入、删除或替换字符等。这时可以考虑三种情况并选择其中编辑距离最小的一种 在 word1 的第 i 个位置插入一个字符使得 word1 和 word2 的前 j 个字符相同此时编辑距离为 dp[i][j-1] 1。 在 word1 的第 i 个位置删除一个字符使得 word1 的前 i-1 个字符和 word2 的前 j 个字符相同此时编辑距离为 dp[i-1][j] 1。 在 word1 的第 i 个位置替换一个字符使得 word1 和 word2 的前 i 个字符和 j 个字符分别相同此时编辑距离为 dp[i-1][j-1] 1。 因此对于每个位置 (i,j)可以使用如下递推公式来计算最小的编辑距离 if (word1[i-1] word2[j-1]) dp[i][j] dp[i-1][j-1];
else dp[i][j] min({dp[i-1][j-1], dp[i-1][j], dp[i][j-1]}) 1; 其中min({dp[i-1][j-1], dp[i-1][j], dp[i][j-1]}) 表示选取上述三种编辑操作中编辑距离最小的一种加上一次操作所需的编辑距离 1即可得到当前位置 (i,j) 的最小编辑距离。 最后返回 dp[w1][w2]即两个字符串的完全匹配所需的最小编辑距离。 复杂度 时间复杂度: O(n*n) 时间复杂度为 O(n*n)其中 n 为两个字符串的长度之和。这是因为算法使用了一个二维数组存储子问题的解需要计算该数组中所有 n*n 个位置的值。 空间复杂度 O(n*n) 空间复杂度也为 O(n*n)因为需要使用一个二维数组来存储所有子问题的解。 如果想要将空间复杂度优化到 O(n) 级别则可以使用滚动数组的技巧只保留当前行和上一行的值即可但会使得代码实现稍微有些复杂。 c 代码
class Solution {
public:int minDistance(string word1, string word2) {int w1 word1.size(), w2 word2.size();// 定义一个二维动态数组 dp其中 dp[i][j] 表示将 word1 的前 i 个字符转换为 word2 的前 j 个字符所需要的最少操作次数。vectorvectorint dp(w11, vectorint(w21, 0));// 初始化第一行和第一列即将一个空字符串转换成另一个字符串所需的最少操作次数。for(int i 0; i w1; i) dp[i][0] i;for(int j 0; j w2; j) dp[0][j] j;// 从第二行和第二列开始按照状态转移方程进行计算。for(int i 1; i w1; i) {for(int j 1; j w2; j) {// 如果 word1 的第 i 个字符与 word2 的第 j 个字符相等则不需要进行任何操作。if(word1[i-1] word2[j-1])dp[i][j] dp[i-1][j-1];// 如果 word1 的第 i 个字符与 word2 的第 j 个字符不相等则需要进行以下三种操作中的一种来进行转换操作// 1. 在 word1 中插入一个字符// 2. 在 word2 中插入一个字符// 3. 替换 word1 中的第 i 个字符或者 word2 中的第 j 个字符。elsedp[i][j] min({dp[i-1][j-1], dp[i-1][j], dp[i][j-1]}) 1;}}// 返回将 word1 转换成 word2 的最少操作次数。return dp[w1][w2];}
};Java代码 首先获取两个字符串的长度即 word1.length() 和 word2.length()分别赋值给变量 m 和 n。接下来创建一个二维数组 dp大小为 (m 1) × (n 1)用于保存计算过程中的编辑距离。这里多加了一行和一列是为了存储空串与 word1 或 word2 的匹配情况。然后通过两个嵌套的循环遍历数组 dp 中的每个位置 (i, j)其中 i 表示 word1 的前 i 个字符j 表示 word2 的前 j 个字符。对于每个位置 (i, j)首先判断 word1 和 word2 在当前位置上的字符是否相同即 word1.charAt(i - 1) word2.charAt(j - 1)。如果相同则说明不需要进行任何编辑操作所以将 dp[i][j] 的值设置为 dp[i - 1][j - 1]即继承上一个位置的编辑距离。如果不相同则需要考虑插入、删除和替换字符三种编辑操作中的最小编辑距离。这里使用 Math.min 方法来取得三者中的最小值并加上一次操作所需的编辑距离 1即 Math.min(Math.min(dp[i - 1][j - 1], dp[i][j - 1]), dp[i - 1][j]) 1然后将结果赋值给 dp[i][j]。最后返回 dp[m][n]即两个字符串的完全匹配所需的最小编辑距离。 class Solution {public int minDistance(String word1, String word2) {// 获取两个字符串的长度int m word1.length();int n word2.length();// 创建一个二维数组来保存编辑距离int[][] dp new int[m 1][n 1];// 初始化dp数组的第一行和第一列for (int i 1; i m; i) {dp[i][0] i;}for (int j 1; j n; j) {dp[0][j] j;}// 逐行逐列计算编辑距离for (int i 1; i m; i) {for (int j 1; j n; j) {// 判断当前字符是否相同if (word1.charAt(i - 1) word2.charAt(j - 1)) {// 如果相同则不需要进行任何编辑操作dp[i][j] dp[i - 1][j - 1];} else {// 如果不同则需要进行插入、删除或替换等操作选取其中编辑距离最小的一种dp[i][j] Math.min(Math.min(dp[i - 1][j - 1], dp[i][j - 1]), dp[i - 1][j]) 1;}}}// 返回编辑距离数组的最后一个元素即两个字符串的完全匹配所需的最小编辑距离return dp[m][n];}
}觉得有用的话可以点点赞支持一下。
如果愿意的话关注一下。会对你有更多的帮助。 每天都会不定时更新哦 人 。
