#Java #动态规划
Feeling and experiences:
给你两个单词?word1
和?word2
, 请返回将?word1
?转换成?word2
所使用的最少操作数 ?。
你可以对一个单词进行如下三种操作:
示例?1:
输入:word1 = "horse", word2 = "ros" 输出:3 解释: horse -> rorse (将 'h' 替换为 'r') rorse -> rose (删除 'r') rose -> ros (删除 'e')
该题的 dp数组定义 , dp数组初始化 ,递推公式都比较难
主要涉及到了 三个操作:
insert,delete,replace
我对 dp数组的定义是:
?达到 word1 第 i 个字母 与到达 word2第 j 个 字母,最小操作数为dp[i][j]
如果用了该定义,就要对dp数组进行初始化!
class Solution {
public int minDistance(String word1, String word2) {
//insert delete replace 操作
//编辑距离问题
//创建dp数组 ,定义: 达到 word1 第 i 个字母 与到达 word2第 j 个 字母,最小操作数为dp[i][j]
int [][]dp = new int[word1.length()+1][word2.length()+1];
//有增删改 三个操作
//初始化:
for(int i =0;i<=word1.length();i++){
dp[i][0] = i;
}
for(int j =0;j<=word2.length();j++){
dp[0][j] = j;
}
//循环遍历,递推
for(int i =1;i<=word1.length();i++){
for(int j=1;j<=word2.length();j++){
//插入删除可以合并:
//word1 删除一个 或者 word2 删除一个(可以衍生为 word1加一个)
if(word1.charAt(i-1) == word2.charAt(j-1)){
//相等则保持上一个状态
dp[i][j] = dp[i-1][j-1];
}else{
//进行 替换操作 , 只需要替换一个 则 加 1
//取最小结果
dp[i][j] = Math.min(Math.min(dp[i-1][j-1],dp[i-1][j]),dp[i][j-1])+1; //Math.min 只能两两比较
}
}
}
return dp[word1.length()][word2.length()];
}
}
这里对 增加 和 删除操作 做了一个巧妙的 合并:
因为 对于word1 增加 一个 字母的操作 ,也就是 word2 删除一个 字母的 操作!
定义状态: 创建一个二维数组 dp
,其中 dp[i][j]
表示将 word1
的前 i
个字符转换为 word2
的前 j
个字符所需的最小编辑操作数。
初始化: 将 dp[i][0]
初始化为 i
,表示将空字符串转换为 word2
的最小编辑操作数为 i
;同理,将 dp[0][j]
初始化为 j
,表示将 word1
转换为空字符串的最小编辑操作数为 j
。
递推关系: 使用嵌套的循环遍历 word1
和 word2
的每个字符,通过比较字符是否相等来决定插入、删除或替换操作。如果字符相等,保持上一个状态;如果不相等,选择插入、删除或替换的最小编辑操作数。
给定两个单词?word1
?和?word2
?,返回使得?word1
?和??word2
?相同所需的最小步数。
每步?可以删除任意一个字符串中的一个字符。
示例 1:
输入: word1 = "sea", word2 = "eat"
输出: 2
解释: 第一步将 "sea" 变为 "ea" ,第二步将 "eat "变为 "ea"
该题 需要对两个字符串进行 删除了
思路基本一致:
class Solution {
public int minDistance(String word1, String word2) {
//要对两个 字符串进行删除操作
//定义dp数组
int[][] dp = new int[word1.length() + 1][word2.length() + 1];
//初始化
for (int i = 0; i < word1.length() + 1; i++) dp[i][0] = i;
for (int j = 0; j < word2.length() + 1; j++) dp[0][j] = j;
//循环,递推
for (int i = 1; i < word1.length() + 1; i++) {
for (int j = 1; j < word2.length() + 1; j++) {
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
}else{
dp[i][j] = Math.min(dp[i - 1][j - 1] + 2,
Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));
}
}
}
return dp[word1.length()][word2.length()];
}
}
定义状态: 创建一个二维数组 dp
,其中 dp[i][j]
表示将 word1
的前 i
个字符转换为 word2
的前 j
个字符所需的最小编辑操作数。
初始化: 将 dp[i][0]
初始化为 i
,表示将空字符串转换为 word2
的最小编辑操作数为 i
;同理,将 dp[0][j]
初始化为 j
,表示将 word1
转换为空字符串的最小编辑操作数为 j
。
递推关系: 使用嵌套的循环遍历 word1
和 word2
的每个字符,通过比较字符是否相等来决定删除、替换或插入操作。如果字符相等,保持上一个状态;如果不相等,选择删除、替换或插入的最小编辑操作数,分别加上对应的成本。
沙上并禽池上暝,
云破月来花弄影。
Fighting!