Prüfungsfrage Anagramm
-
Okay klingt einleuchtend, danke dir, nur hab ich da ein weiteres Problem - Alphabetisches ordnen eines Array ohne Bib.-Funktion.
Klingt ziemlich aufwendig oder gibts da ne einfache Methode?
-
Zähle einfach, wie oft jeder Buchstabe vorkommt.
-
Ja das hab ich mir auch gedacht nur dann kann ich ne switch Anweisung oder sowas für das ganze Alphabet machen, bin mir ziemlich sicher das es einfacher geht -> Zeit ist Geld in der Prüfung
-
Aber so hätte er direkt nochmal diverse Sortieralgorithmen wiederholen können
Quicksort, Bubblesort und wie sie alle heissen, Wikipedia hilft.
EDIT: Nein, einfach ein array anlegen mit 26 Elementen (für jeden Buchstaben eines) , dann greifst einfach über
array[aktueller_buchstabe-97] auf das Arrayelement zu und erhöhst dieses um 1, vorher natürlich alle mit 0 initialisieren. 97 weil es Kleinbuchstaben sind und das kleine a den Wert 97 hat. Dann durchläufst noch mal das Array und schaust ob irgendein Wert ungleich 0 oder ungleich 2 ist, dann sind die Strings unterschiedlich.
-
machst du 2 arrays int[26], alle elemente mit dem gleichen wert initialiseren, dann in beiden arryas 'array[buchstabe-'a']++' und zum schluss beide arrays vergleichen. sind beide gleich, dann haben beide wörter die gleiche buchstabenmenge.
-
***
-
Okay danke für eure antworten, werd das alles mal durchgehen
-
Noch einfacher wäre es ja mit einem Array[26], beim einem String wird addiert, beim anderen subtrahiert. Wenn danach alle Elemente 0 sind ist es ein Anagram.
-
noch speicherschonender wäre die schummelversion: nimm 2 doubles (weil riesige werte entstehen werden), setze sie auf 0, für jedes zeichen in string_1 wir double_1 um 2^zeichen erhöht und das gleiche für string_2. sind beide doubles gleich, dann sind die strings (mit hoher wahrscheinlichkeit) gleich.
-
mogel-freak schrieb:
dann sind die strings (mit hoher wahrscheinlichkeit) gleich.
wollte sagen: die menge der zeichen ist gleich, naja, ihr wisst schon...
-
Nette Idee, hat nur zwei Probleme: (a) wirst du bei entsprechend langen Wörtern an die Genauigkeitsgrenze von double stoßen (ja, double verarbeitet problemlos Zahlen bis jenseits 10100, allerdings nicht mehr auf die letzte Ziffer exakt) und (b) ist 2n+2n==2n+1, was deine "hohe Wahrscheinlichkeit" doch etwas drückt - "aax" wäre bei deiner Berechnung ein Anagramm von "bww".
-
zugegeben, das war 'ne dumme idee. sollte sowas ähnliches werden wie ein hashwert-vergleich und 26^buchstabe schien mir für 'double' auch etwas zu hoch, deshalb hab' ich mal mit der 2 angefangen.