Anagramme (Schüttelwörter) gruppieren

2 Lösungen

#343

Fortgeschrittener - C++ von JKooP - 13.03.2021 um 12:41 Uhr

Von einem Anagramm oder auch deutsch Schüttelwort spricht man,
wenn man durch Umstellen der vorhandenen Zeichen eines Wortes ein neues sinnvolles Wort bilden kann.
Oft werden Anagramme mit Palindromen verwechselt, wobei ein Anagramm auch gleichzeitig
ein Palindrom sein kann, z.B.: LAGERREGAL – REGALLAGER.

ANNA – ANNA hingegen ist kein Anagramm, sondern ein Palindrom,
obwohl es wegen des Gleichklangs ANA oft irrtümlich so bezeichnet wird.

Gegeben ist eine Liste bestehend aus verschiedenen Wörtern.
list = { "eat", "tea", "tan", "ate", "nat", "bat" };

Schreibe eine Methode/Funktion, die die Liste list auf Anagramme hin überprüft
und die Ergebnisse in einer neuen Liste gruppiert zurückgibt.

result = { {"bat"}, {"nat", "tan"}, {"ate", "eat", "tea"} }

Die Reihenfolge der Rückgabe in der List ist nicht entscheidend.
Wörter, die keine Anagramme bilden, sollen ebenfalls als Einzelwort in die Ergebnisliste aufgenommen werden.
Je nach Programmiersprache oder Vorliebe können statt Listen auch Arrays oder Tupel verwendet werden.

Viel Spaß

Bitte melden Sie sich an um zur Aufgabenbeschreibung eine Frage zu stellen.

Frage stellen

Bitte melden Sie sich an um eine Lösung einzureichen.

Lösung einreichen

von JKooP (18090 Punkte) - 23.04.2021 um 09:29 Uhr

C++ 17

C-Code

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>
using namespace std;

vector<vector<string>> group_anagrams(vector<string>& vs) {
    vector<vector<string>> vr;
    unordered_map<string, vector<string>> um;

    for (auto i{ 0 }; i < vs.size(); i++) {
        auto t{ vs[i] };
        sort(t.begin(), t.end());
        um[t].push_back(vs[i]);
    }
    for (const auto& i : um)
        vr.push_back(i.second);

    return vr;
}

int main()
{
    vector<string> s{ { "eat", "tea", "tan", "ate", "nat", "bat" } };

    for (const auto& i : group_anagrams(s)) {
        for (const auto& k : i)
            cout << k << ", ";
        cout << endl;
    }
}