Đang tải…
Đang tải…
Khoảng cách Levenshtein: số phép chèn/xóa/thay tối thiểu để biến chuỗi này thành chuỗi kia, dựng từng ô một.
Cơ sở: biến một tiền tố thành chuỗi rỗng tốn đúng độ dài của nó.
1int editDistance(String a, String b) {2 int m = a.length(), n = b.length();3 int[][] dp = new int[m+1][n+1];4 for (int i = 0; i <= m; i++) dp[i][0] = i;5 for (int j = 0; j <= n; j++) dp[0][j] = j;6 for (int i = 1; i <= m; i++)7 for (int j = 1; j <= n; j++)8 if (a.charAt(i-1) == b.charAt(j-1))9 dp[i][j] = dp[i-1][j-1];10 else11 dp[i][j] = 1 + Math.min(dp[i-1][j-1],12 Math.min(dp[i-1][j], dp[i][j-1]));13 return dp[m][n];14}