[Leetcode 72]编辑距离 Edit Distance

时间:2023-03-08 16:28:09

【题目】

Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.

You have the following 3 operations permitted on a word:

  1. Insert a character
  2. Delete a character
  3. Replace a character

Example 1:

Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation:
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')
把单词1变成单词2,可以修改/删除/插入,最少需要几步

【思路】

动态规划dp[i][j],i为原数据,j为现数据

三种情况plus、del、rep,求min+1(步骤)

【代码】

class Solution {
public int minDistance(String word1, String word2) {
int m=word1.length();
int n=word2.length();
int cost[][]=new int[m+1][n+1];
for(int i=0;i<m;i++){
cost[i][0]=i;}
for(int j=0;j<n;j++){
cost[0][j]=j;} for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(word1.charAt(i)==word2.charAt(j)){
cost[i+1][j+1]=cost[i][j];}
else{
int plus=cost[i+1][j];
int del=cost[i][j+1];
int rep=cost[i][j];
cost[i+1][j+1]=Math.min(plus,Math.min(del,rep))+1;
}
}
}
return cost[m][n];
} }