Loading…
Loading…
The Levenshtein distance: the minimum number of insertions, deletions, or substitutions to turn one string into another, built cell by cell.
Base cases: turning a prefix into an empty string costs its length.
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}