Ajutor algoritm

[•moon]

Puteti va rog sa-mi descrieti solutia de complexitate O(n*Logn) la aceasta problema ? Multumesc !

Un cuvânt este anagramã a altui cuvânt dacã este format din exact aceleaºi litere, aranjate într-o
altã ordine. Exemplu: caras si scara.
b) Dându-se o mulþime de n cuvinte peste alfabetul {a ,........, z}
sã se verifice dacã printre elementele mulþimii date existã anagrame.

[•PlayLikeNeverB4]

Ma gandesc ca e ceva de genul:
Pentru fiecare cuvant, ii sortezi literele componente alfabetic. Apoi, sortezi alfabetic toate cuvintele intre ele. In final, verifici daca exista cuvinte egale pe pozitii consecutive. Complexitatea O(N*logN) vine de la sortare.

[•truenight]

Daca am folosi un array 2D in care, pentru fiecare cuvant, retinem de cate ori se repeta fiecare litera din cuvant si dupa aia comparam, s-ar incadra in O(N*logN)?

[•PlayLikeNeverB4]

A ta e O(N*nr de litere din alfabet * log (nr de litere)) . Daca cuvintele sunt mai lungi decat numarul de litere din alfabet, atunci e mai eficienta decat solutia mea pentru ca ai de facut mai putine comparatii la sortare. Insa, pentru stringuri exista functii predefinite, deci e mai comod.

[•stocarul]

Ma gandesc ca e ceva de genul:
Pentru fiecare cuvant, ii sortezi literele componente alfabetic. Apoi, sortezi alfabetic toate cuvintele intre ele. In final, verifici daca exista cuvinte egale pe pozitii consecutive. Complexitatea O(N*logN) vine de la sortare.

Vezi că soluţia ta are o complexitate O(N * lngCuvânt * (log(N) + log(lngCuvânt))

Compararea a două cuvinte nu se face în timp constant. Se face în O(lungimeCuvânt)

[•PlayLikeNeverB4]

Da, ai dreptate. Eu am considerat ca se poate neglija lungimea cuvantului, iar daca e prea mare atunci se trece la cealalta varianta.

[•S7012MY]

Puteti va rog sa-mi descrieti solutia de complexitate O(n*Logn) la aceasta problema ? Multumesc !

Un cuvânt este anagramã a altui cuvânt dacã este format din exact aceleaºi litere, aranjate într-o
altã ordine. Exemplu: caras si scara.
b) Dându-se o mulþime de n cuvinte peste alfabetul {a ,........, z}
sã se verifice dacã printre elementele mulþimii date existã anagrame.

Pentru fiecare cuvant il sortezi si il bagi intr-un hash. Daca il mai gasesti in hash inseamna ca ai anagrama.