Алгоритми та структури даних · Senior · Запитання 59 з 75
Яку структуру обрати для автодоповнення, що ранжує підказки за популярністю?
- ✓Правильна відповідь: Trie з топ-підказками, закешованими в кожному вузлі
- 2Хеш-таблицю від повних слів лише до їхніх лічильників
- 3Відсортований масив, який переглядають від початку
Пояснення
Trie знаходить вузол префікса за O(довжина префікса); кеш топ-k у вузлі позбавляє від обходу всього піддерева на кожне натискання клавіші. Звичайна map не вміє ефективно видавати слова за префіксом.