Levenshtein distance
unknown
java
2 years ago
831 B
6
Indexable
public int partDist(String w1, String w2, int[][]m) { int subCost = 0; for(int j = 1; j < w2.length()+1;j++) { for(int i = 1; i < w1.length()+1; i++) { if(w1.charAt(i-1)==w2.charAt(j-1)) subCost = 0; else subCost = 1; m[i][j] = Math.min(m[i-1][j] + 1, //delete a character Math.min(m[i][j-1] + 1, //insert a character m[i-1][j-1] + subCost));//sub a character } } return m[w1.length()][w2.length()]; } int distance(String w1, String w2) { int[][] m = new int[w1.length()+1][w2.length()+1]; for(int i = 1; i < 1 + w1.length();i++) m[i][0] = i; for(int i = 1; i < 1 + w2.length();i++) m[0][i] = i; return partDist(w1, w2,m); }
Editor is loading...