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 s1, String s2) {2 int len1 = s1.length(), len2 = s2.length();3 int[][] dp = new int[len1+1][len2+1];4 for (int i = 0; i <= len1; i++) dp[i][0] = i; // delete each prefix char5 for (int j = 0; j <= len2; j++) dp[0][j] = j; // insert each prefix char6 for (int i = 1; i <= len1; i++)7 for (int j = 1; j <= len2; j++)8 if (s1.charAt(i-1) == s2.charAt(j-1)) // same character?9 dp[i][j] = dp[i-1][j-1]; // reuse diagonal10 else11 dp[i][j] = 1 + Math.min(dp[i-1][j-1], // 1 + min(diag, up, left)12 Math.min(dp[i-1][j], dp[i][j-1]));13 return dp[len1][len2]; // minimum edit distance14}