Алгоритми та структури даних · Middle · Запитання 46 з 75
Що вимірює відстань Левенштейна (редакційна відстань)?
- 1Різницю в довжині двох рядків
- 2Кількість позицій, де відрізняються два рядки однакової довжини
- ✓Правильна відповідь: Мінімум вставок, видалень і замін, щоб перетворити один рядок на інший
Пояснення
Її обчислюють таблицею DP за O(n × m), і на ній працюють перевірка правопису й підказки «можливо, ви мали на увазі...?». Кількість різних позицій у рядках однакової довжини - це відстань Геммінга.