Groeperen en indelen met een map

Veel opgaven vragen je om elementen die iets gemeen hebben te groeperen. Een koppeling van sleutel naar bakje maakt daar één nette doorgang van. 🗂️

De hele truc draait om het kiezen van een sleutel die gelijk is voor elementen in dezelfde groep. Als dat klopt, is de rest eenvoudig.

Gebruik defaultdict(list), zodat elke nieuwe sleutel met een leeg bakje begint. Je voegt elementen toe zonder ooit te controleren of de sleutel bestaat.

Bereken voor elk element de sleutel en voeg het element toe aan het bakje van die sleutel. Met één regel per element groepeer je alles.

Anagrammen hebben dezelfde gesorteerde letters, dus de gesorteerde tekenreeks is de perfecte groepssleutel. Sorteer één keer en groepeer daarna op die sleutel.

Wanneer sorteren te traag is, kun je ook een tuple met lettertellingen als sleutel gebruiken. Tupels zijn hashbaar en passen daarom probleemloos in een dict.

Groepeer getallen op rest, pariteit of lengte door alleen de sleutel te veranderen. Het patroon blijft bij verschillende opgaven hetzelfde.

Als waarden binnen een klein bereik vallen, plaats je elke waarde in een geïndexeerd bakje en lees je de bakjes op volgorde uit. Dat levert bijna lineaire sortering op.

Na het verdelen over bakjes bestaat het antwoord meestal uit de values van de dict. Zet ze om in een lijst als de beoordelaar de groepen zelf verwacht.

Als je alleen de groottes van groepen nodig hebt, kun je de elementen in een Counter tellen of aan het einde de lengtes optellen. Kies wat de vraag werkelijk vraagt.

Groeperen met een koppeling kost O(n) in plaats van dat je elk paar vergelijkt. De gehashte sleutel doet het vergelijkingswerk voor je.

Groepeer door de sleutel van elk element in één doorgang van O(n) onder te brengen in een defaultdict-bakje. Kies de sleutel zorgvuldig en groepsopgaven worden een stuk eenvoudiger. 🚀