Revizia anterioară Revizia următoare
Holiday
Autobuze2
Litere2
- Două cuvinte fac parte din acelaşi grup dacă sunt formate din aceleaşi litere, repetate de oricâte ori.
Vom lua astfel fiecare cuvânt în parte şi vom marca toate cele 26 litere ale alfabetului englez ('a' - 'z') cu 1, dacă litera apare în cuvânt respectiv cu 0, dacă nu apare. Vom obţine astfel un şir binar de lungime 26. Putem privi acest şir binar ca fiind un număr scris în baza 2. Putem transforma acest număr în baza 10, reformulând afirmaţia iniţială astfel:
- Două cuvinte fac parte din acelaşi grup dacă numărul astfel obţinut asociat celor două cuvinte este acelaşi.
Deci, numărul de grupuri va fi egal cu numărul de valori distincte asociate numerelor. Pentru a determina acest număr ne vom folosi de o structură de date tip Hash sau de o sortare (aceasta fiind teoretic, soluţia de complexitate mai mare).
Timpul de execuţie al acestei probleme se putea mări destul de uşor dacă în program se foloseau elemente din STL sau tipul de date string, care se miscă mai lent în practică.
Treesmen
