# Edit Distance

• 插入一个字符
• 删除一个字符
• 替换一个字符

``````给出 work1="mart" 和 work2="karma"

``````

## Solution

res[i][j]表示Edit Distance between X数组的前i个元素以及Y数组的前j个元素，或者the minimum # of operations to convert X前i个元素 into Y的前j个元素

## Code

``````public class Solution {
public int minDistance_1(String word1, String word2) {
if(word1==word2) return 0;
int len1 = word1.length();
int len2 = word2.length();
int[][] dp = new int[len1+1][len2+1];

for(int i=0;i<=len1;i++)
dp[i][0] = i;
for(int i=0;i<=len2;i++)
dp[0][i] = i;

for(int i=1;i<=len1;i++){
for(int j=1;j<=len2;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],Math.min(dp[i][j-1],dp[i-1][j-1]))+1;
}
}
}
return dp[len1][len2];
}

public int minDistance(String word1, String word2) {
if(word1==word2) return 0;
int len1 = word1.length();
int len2 = word2.length();
int[] dp = new int[len2+1];

for(int i=0;i<=len2;i++)
dp[i] = i;

for(int i=1;i<=len1;i++){
int upperLeftBak = dp[0];
dp[0] = i;
for(int j=1;j<=len2;j++){
int upperLeft = upperLeftBak;
upperLeftBak = dp[j];
if(word1.charAt(i-1)==word2.charAt(j-1)) dp[j] = upperLeft;
else{
dp[j] = Math.min(dp[j],Math.min(dp[j-1],upperLeft))+1;
}
}
}
return dp[len2];
}
}
``````