O rezolvare brute-force a problemei mentine o lista a tuturor cuvintelor si rezolva operatiile de tip $0 w$ si $1 w$ in timp $O(L)$, iar operatiile de tip $2 w$ si $3 w$ in timp $O(N*L)$, unde $N$ este numarul de cuvinte din lista, iar $L$ lungimea cuvantului $w$. Memoria folosita este $O(LungTot)$, unde $LungTot$ este lungimea totala a cuvintelor din lista. O astfel de abordere ar trebui sa obtina in jur de 30 de puncte, iar o sursa demonstrativa se afla aici.

Solutia eficienta foloseste o structura de date arborescenta cunoscuta sub numele de *Trie*. Spre deosebire de alte structuri de date, intr-un trie cheile nu sunt identificate unic printr-un singur nod, ci prin drumul de la radacina trie-ului pana la un anumit nod. Astfel, fiecare nod are un numar de fii egal cu dimensiunea alfabetului folosit, iar fiecare muchie catre un fiu este etichetata cu litera corespunzatoare din alfabet. Pornind de la radacina (careia i se asociaza sirul vid), fiecarui nod i se asociaza (va memora informatii suplimentare despre) cheia al carei nume se obtine prin concatenarea etichetelor tuturor muchiilor de pe drumul de la radacina trie-ului pana in nodul respectiv. Aceasta permite executarea tuturor operatiilor in timp $O(L)$. Spatiul de memorie folosit depinde de structura cuvintelor din lista, mai exact de prefixele lor comune. Totusi, ea nu va depasi $O(LungTot * |Sigma|)$, unde $Sigma$ este alfabetul folosit (in cazul de fata $|Sigma|=26$). Mai multe informatii despre structura de date vezi gasi 'aici':http://en.wikipedia.org/wiki/Trie. De asemenea, un tutorial util se afla pe 'TopCoder':http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=usingTries.

Solutia eficienta foloseste o structura de date arborescenta cunoscuta sub numele de *Trie*. Spre deosebire de alte structuri de date, intr-un trie cheile nu sunt identificate prin informatia dintr-un singur nod, ci prin drumul de la radacina trie-ului pana la un anumit nod. Astfel, fiecare nod are un numar de fii egal cu dimensiunea alfabetului folosit, iar fiecare muchie catre un fiu este etichetata cu litera corespunzatoare din alfabet. In figura de mai jos este ilustrat starea trie-ului din exemplu, dupa ce toate operatiile au fost executate. Pentru simpitate grafica, am eliminat din desen muchiile irelevante si am reprezentat ca informatie intr-un nod doar numarul de cuvinte care corespund cheii nodului respectiv:
 
p=. !problema/trie?trie.png!
 
Pornind de la radacina (careia i se asociaza sirul vid), fiecarui nod i se asociaza (va memora informatii suplimentare despre) cheia al carei nume se obtine prin concatenarea etichetelor tuturor muchiilor de pe drumul de la radacina trie-ului pana in nodul respectiv (in desen este evidentiat modul in care putem identifica nodul a carui cheie este $"lat"$).
 
Acest mod de gestionare a listei de cuvinte permite executarea fiecarei operatii in timp $O(L)$. Spatiul de memorie folosit depinde de structura cuvintelor din lista, mai exact de prefixele lor comune. Totusi, el nu va depasi $O(LungTot * |Sigma|)$, unde $Sigma$ este alfabetul folosit (in cazul de fata $|Sigma|=26$). Mai multe informatii despre structura de date vezi gasi 'aici':http://en.wikipedia.org/wiki/Trie. De asemenea, un tutorial util se afla pe 'TopCoder':http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=usingTries.

h2. Aplicatii

Ideile din spatele aceastei structuri de date pot fi adaptate si integrate intr-o larga varietate de algoritmi. O aplicatie ingenioasa este solutia problemei 'xormax':http://infoarena.ro/problema/xormax. O alta problema, care se foloseste de cautare binara pe niveluri intr-un trie este 'ratina':http://infoarena.ro/problema/ratina. De asemenea, cu ajutorul unui trie pot fi rezolvate si urmatoarele:

Ideile din spatele aceastei structuri de date pot fi adaptate si integrate intr-o larga varietate de algoritmi. O aplicatie ingenioasa este solutia problemei 'xormax':http://infoarena.ro/problema/xormax. O alta problema, care se foloseste de cautare binara pe niveluri intr-un trie este 'ratina':http://infoarena.ro/problema/ratina. De asemenea, cu ajutorul unui trie pot fi rezolvate si:

* 'sub':http://infoarena.ro/problema/sub (infoarena)
* 'dictree':http://infoarena.ro/problema/dictree (infoarena)