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*. 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*. 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.

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 in 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 urmatoarele:

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