leetcode 72. 编辑距离
程序员文章站
2022-07-12 08:54:35
...
解决思路:
动态规划
状态数组的含义 dp[i][j]: word1的前i个字符--->word2的前j个字符的最小步数
dp[i][j]= dp[i-1][j-1] word1[i]==word2[j]
min(dp[i][j-1],dp[i-1][j],dp[i-1][j-1])+1 word1[i]!=word2[j]
代码:
public static void main(String[] args) {
String word1 = "horse";
String word2 = "ros";
int num = minDistance(word1, word2);
System.out.println(num);
}
/**
* @Description: 状态数组的含义 dp[i][j]: word1的前i个字符--->word2的前j个字符的最小步数
* dp[i][j]= dp[i-1][j-1] word1[i]==word2[j]
* min(dp[i][j-1],dp[i-1][j],dp[i-1][j-1])+1 word1[i]!=word2[j]
* @Date: 2020/2/6 10:39
* @Author: fuguowen
* @Return
* @Throws
*/
public static int minDistance(String word1, String word2) {
int i=word1.length();
int j=word2.length();
if(i==0){
return j;
}
if(j==0){
return i;
}
//先处理左边界和上边界,然后递推
int[][] arr=new int[i+1][j+1];
arr[0][0]=0;
//不断添加单词
for(int p=1;p<=j;p++){
arr[0][p]=arr[0][p-1]+1;
}
//不断删除单词
for(int q=1;q<=i;q++){
arr[q][0]=arr[q-1][0]+1;
}
for(int p=1;p<=i;p++){
for(int q=1;q<=j;q++){
if(word1.charAt(p-1)==word2.charAt(q-1)){
arr[p][q]=arr[p-1][q-1];
}else{
arr[p][q]=Math.min(Math.min(arr[p-1][q-1],arr[p][q-1]),arr[p-1][q])+1;
}
}
}
return arr[i][j];
}
上一篇: LeetCode 72. 编辑距离