/*
* The given code is provided to assist you to complete the required tasks. But the
* given code is often incomplete. You have to read and understand the given code
* carefully, before you can apply the code properly.
*/
/*
* Please review Lecture 7 Algorithms Part III, slides 10-14 to complete this task.
* */
/*
* EditCost defines three character edit costs. INSERT and DELETE will cost 1, and REPLACE will cost 2.
* Do not modify the character edit costs. Otherwise, your answers will not be marked correctly.
* */
enum EditCost
{
INSERT (1),
DELETE (1),
REPLACE (2);
private final int costValue;
EditCost(int value) {
this.costValue = value;
}
public int getEditCost(){
return this.costValue;
}
}
public class EditDistance {
/* This method computes the minimal total cost of a sequence of character edits between two strings.
* The costs of character edits are defined in EditCost enum
* @param seq1 the original string.
* @param seq2 the target string.
* @return the minimal cost of the character edits.
* */
public static int minDistance(String s1, String s2){
// TODO: Complete this method
// START YOUR CODE
int n = s1.length();
int m = s2.length();
// 有一个字符串为空串
if (n * m == 0) {
return n + m;
}
// DP 数组
int[][] D = new int[n + 1][m + 1];
// 边界状态初始化
for (int i = 0; i < n + 1; i++) {
D[i][0] = i;
}
for (int j = 0; j < m + 1; j++) {
D[0][j] = j;
}
// 计算所有 DP 值
for (int i = 1; i < n + 1; i++) {
for (int j = 1; j < m + 1; j++) {
int left = D[i - 1][j] + 1;
int down = D[i][j - 1] + 1;
int left_down = D[i - 1][j - 1];
if (s1.charAt(i - 1) != s2.charAt(j - 1)) {
left_down += 2;
}
D[i][j] = Math.min(left, Math.min(down, left_down));
}
}
return D[n][m];
// END YOUR CODE
}
}