【题目】
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:
- Insert a character
- Delete a character
- 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];
}
}