Algorithmen und Datenstrukturen · Junior · Frage 44 von 75
Wie prüft man in O(n), ob zwei Strings Anagramme sind?
- 1Prüfen, dass beide Strings gleich lang sind
- 2Prüfen, dass jedes Zeichen des ersten im zweiten vorkommt
- 3Die Zeichen beider Strings zählen und die Zählungen vergleichen
Antwort zeigen
Richtige Antwort: Die Zeichen beider Strings zählen und die Zählungen vergleichen
Erklärung
Zähle die Zeichen des ersten Strings in einer Map, ziehe den zweiten ab und prüfe, dass alle Zähler null sind. Gleiche Länge reicht nicht, und die Prüfung „jedes Zeichen kommt vor“ ignoriert, wie oft es vorkommt („aab“ vs. „abb“). Beide Strings zu sortieren funktioniert auch, kostet aber O(n log n).