Алгоритми та структури даних · Senior · Запитання 67 з 75
Як за O(n) перевірити, що два слова відрізняються на одне редагування?
- 1Обчислити повну таблицю Левенштейна й перевірити на 1
- 2Відсортувати обидва слова й порівняти результати
- ✓Правильна відповідь: Два вказівники з дозволом на один пропуск чи розбіжність
Пояснення
Якщо довжини відрізняються більш ніж на один, відповідь - ні. Інакше рухайте вказівники разом і на першій розбіжності пропустіть символ у довшому слові (або в обох, якщо довжини рівні). Повне DP - O(n × m).