Algorytmy i struktury danych · Senior · Pytanie 59 z 75
Jakiej struktury użyć do autouzupełniania, które układa podpowiedzi według popularności?
- ✓Poprawna odpowiedź: Trie z najlepszymi podpowiedziami zapamiętanymi w każdym węźle
- 2Mapy z pełnych słów tylko na ich liczniki
- 3Posortowanej tablicy przeglądanej od początku
Wyjaśnienie
Trie znajduje węzeł prefiksu w O(długość prefiksu); zapamiętanie top-k w węźle oszczędza przechodzenie całego poddrzewa przy każdym naciśnięciu klawisza. Zwykła mapa nie potrafi wydajnie wypisać słów po prefiksie.