Реализации алгоритмов/Расстояние Левенштейна: различия между версиями

Содержимое удалено Содержимое добавлено
Строка 220:
 
public static int levenstain(@Nonnull String str1, @Nonnull String str2) {
int[] D1Di_1 = new int[str2.length() + 1];
int[] D2Di = new int[str2.length() + 1];
 
for (int j = 0; j <= str2.length(); j++) {
D2Di[j] = j;
}
 
for (int i = 1; i <= str1.length(); i++) {
System.arraycopy(D2Di, 0, D1Di_1, 0, D1Di_1.length);
D2Di[0] = i;
 
for (int j = 1; j <= str2.length(); j++) {
int cost = (str1.charAt(i - 1) != str2.charAt(j - 1)) ? 1 : 0;
D2Di[j] = min(
D1Di_1[j] + 1,
D2Di[j - 1] + 1,
D1Di_1[j - 1] + cost
);
}
}
 
return D2Di[D2Di.length - 1];
}