Algorytmy i struktury danych · Middle · Pytanie 46 z 75
Co mierzy odległość Levenshteina (odległość edycyjna)?
- 1Różnicę długości dwóch napisów
- 2Liczbę pozycji, na których różnią się dwa napisy równej długości
- ✓Poprawna odpowiedź: Minimum wstawień, usunięć i zamian, aby zmienić jeden napis w drugi
Wyjaśnienie
Liczy się ją tabelą DP w O(n × m) i napędza sprawdzanie pisowni oraz podpowiedzi „czy chodziło ci o...?”. Liczba różniących się pozycji w napisach równej długości to odległość Hamminga.