Skip to content

Instantly share code, notes, and snippets.

@Lazyb0x

Lazyb0x/EditDistance.java

Last active Feb 4, 2020
Embed
What would you like to do?
Leetcode 72:编辑距离
package dynamic_program;
// Leetcode 72 编辑距离
// 自底向上的方法
class Solution72 {
//保存距离
int[][] dist;
//保存操作。值 0~3 分别是:0跳过,1插入,2删除,3替换
int[][] act;
public int minDistance(String word1, String word2) {
int l1 = word1.length();
int l2 = word2.length();
dist = new int[l1+1][l2+1];
act = new int[l1+1][l2+1];
for (int i=0; i<=l1; i++) {
dist[i][0] = i;
act[i][0] = 2; //删除
}
for (int j=0; j<=l2; j++) {
dist[0][j] = j;
act[0][j] = 1; //插入
}
for (int i=1; i<=l1; i++) {
for (int j=1; j<=l2; j++) {
if (word1.charAt(i-1)==word2.charAt(j-1)) {
dist[i][j] = dist[i-1][j-1];
act[i][j] = 0; //跳过
}
else {
int add = dist[i][j-1]+1;
int rem = dist[i-1][j]+1;
int repl = dist[i-1][j-1]+1;
if (repl<add && repl<rem) {
dist[i][j] = repl;
act[i][j] = 3; //替换
}
else if (add<rem) {
dist[i][j] = add;
act[i][j] = 1; //插入
}
else {
dist[i][j] = rem;
act[i][j] = 2; //删除
}
}
}
}
printOperations(act, l1, l2, word1, word2);
return dist[l1][l2];
}
public void printOperations(int[][] act,int i,int j, String w1, String w2) {
System.out.println(w1 + " -> " + w2 + ":");
while (i!=0 && j!=0) {
String tmp;
String s = "";
switch (act[i][j]) {
case 0:
//s = "(跳过)";
i--;
j--;
break;
case 1:
tmp = w1.substring(0, i) + w2.charAt(j-1) + w1.substring(i+1);
s = String.format("%s -> %s (插入 '%c')\n", w1, tmp, w2.charAt(j-1));
w1 = tmp;
j--;
break;
case 2:
tmp = w1.substring(0, i-1) + w1.substring(i);
s = String.format("%s -> %s (删除 '%c')\n", w1, tmp, w1.charAt(i-1));
w1 = tmp;
i--;
break;
case 3:
tmp = w1.substring(0, i-1) + w2.charAt(j-1) + w1.substring(i);
s = String.format("%s -> %s (将 '%c' 替换为 '%c')\n",
w1, tmp, w1.charAt(i-1), w2.charAt(j-1));
w1 = tmp;
i--;
j--;
break;
}
System.out.print(s);
}
}
}
public class EditDistance {
public static void main(String[] args) {
Solution72 s = new Solution72();
System.out.println(s.minDistance("horse", "ros"));
System.out.println(s.minDistance("intention", "execution"));
System.out.println(s.minDistance("consistent", "constraint"));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.