CS计算机代考程序代写 algorithm /*

/*
* 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 } }