Java实现 LeetCode 72 编辑距离
2023-09-14 08:58:07 时间
72. 编辑距离
给定两个单词 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’)
class Solution {
public int minDistance(String word1, String word2) {
int len1 = word1.length();
int len2 = word2.length();
//处理有空字符串的特殊情况
if (len1 * len2 == 0)
return len1 + len2;
String longerStr = len1 > len2 ? word1 : word2;
String shorterStr = len1 > len2 ? word2 : word1;
int shorterOne = Math.min(len1, len2);
//dp数组长度为两字符串中长度较小的那个
int[] dp = new int[shorterOne + 1];
//初始化dp数组
for (int i = 0; i < shorterOne + 1; i++) {
dp[i] = i;
}
//从长度较长的字符串开始遍历,注意j从1开始,取第j-1位字符,因此结束位置是 longerStr.length()
for (int j = 1; j <= longerStr.length(); j++) {
// 每次遍历短字符串前,先给left赋初始值
int left = j;
//遍历长度较短的字符串,同样从1开始,取第i-1位字符,因此结束位置是 shortStr.length()
for (int i = 1; i <= shorterStr.length(); i++) {
int updateDown = dp[i] + 1;
int updateLeft = left + 1;
int updateLeftDown = dp[i - 1];
//如果当前字符不匹配,左下角的那个值要加一,表示替换当前字符
if (longerStr.charAt(j - 1) != shorterStr.charAt(i - 1)) {
updateLeftDown++;
}
//获取较小的那个
int min = Math.min(updateLeft, Math.min(updateDown, updateLeftDown));
//因为 dp[i - 1]后面用不到了,替换为当前的left值
dp[i - 1] = left;
//如果遍历到最后一个时,直接更新dp[i]
if(i == dp.length - 1){
dp[i] = min;
}else{
//否则更新左边的值,而不是直接更新 dp[i],因为下个循环需要用到原来的 dp[i]以及刚更新的left
left = min;
}
}
}
return dp[shorterOne];
}
}
相关文章
- Java实现 LeetCode 763 划分字母区间(暴力)
- Java实现 LeetCode 728 自除数(暴力)
- Java实现 LeetCode 710 黑名单中的随机数(黑白名单)
- Java实现 LeetCode 659 分割数组为连续子序列 (哈希)
- Java实现 LeetCode 639解码方法 2(递推)
- Java实现 LeetCode 589 N叉树的前序遍历(遍历树)
- Java实现 LeetCode 504 七进制数
- Java实现 LeetCode 435 无重叠区间
- Java实现 LeetCode 363 矩形区域不超过 K 的最大数值和
- Java实现 LeetCode 347 前 K 个高频元素
- Java实现 LeetCode 326 3的幂
- Java实现 LeetCode 273 整数转换英文表示
- Java实现 LeetCode 268 缺失数字
- Java实现 LeetCode 234 回文链表
- Java实现 LeetCode 227 基本计算器 II(二)
- Java实现 LeetCode 203 移除链表元素
- Java实现 LeetCode 101 对称二叉树
- Java实现 LeetCode 94 二叉树的中序遍历
- Java实现 LeetCode 30 串联所有单词的子串
- Java实现 LeetCode 19删除链表的倒数第N个节点
- Java 蓝桥杯 算法训练 字符串的展开 (JAVA语言实现)
- Java Instrumentation 内存马——主要是利用Instrumentation Java API来做内存注入,会用到反射机制,文中提到检测思路:注入jar包-> dump已加载class字节码->反编译成java代码-> 源码webshell检测