algorithm: find whether the array contains a string with one character difference from the given string
-
Trie ist richtig, auch wenns komisch aussieht.
-
Ich sehe new aber kein delete => Speicherleck! Abhilfe: Smartpointer.
-
Regel der großen Drei/Fünf nicht beachtet. Das kommt davon, wenn man denkt, selber Speicher verwalten zu müssen.
-
@manni66: stimmt. trie delete ist noch nicht implementiert.
sonst comments zu algo?
-
Ich bin irgendwie nicht so glücklich damit, dass du deinen Algorithmus ohne Not auf Kleinbuchstaben beschränkst. Lass doch einfach alle möglichen Zeichen zu! Derzeit baut dein Programm totalen Mist, wenn ein nicht-Kleinbuchstabe kommt. Es wäre ja sogar einfacher, wenn du diese Beschränkung einfach weg ließest.
-
algoboy schrieb:
sonst comments zu algo?
Sieht für mich ganz falsch aus. Hab ein ungutes Gefühl, wie das erste Zeichen platt als Treffer verbucht wird, da könnte "ba" das "panana" verdecken. Hab ein ungutes Gefühl, wie bei der ersten Möglichkeit des Überspringens diese und nur diese benutzt wird, da könnte "benan" ein "banena" verdecken.
Auf jeden Fall musst Du wegkommen vom Erstellen von Testfällen per Hand. Bau eine lahme narrensicherere Referenzimplementierung und erzeuge in der main zufällige Strings und lass Deine Implementierung 1000000 mal gegen die Referenzimplementierung antreten. Sorge per Feintuning (min_wordlength, max_wordlength, vec_size) dafür, daß nicht fast alle Testfälle true und nicht fast alle Testfälle false ergeben.
-
KN4CK3R schrieb:
Trie ist richtig, auch wenns komisch aussieht.
Oh, wieder was gelernt. Hab ich noch nie gehört und sah einfach nur falsch aus.
-
Ich hätte ja Levenshtein Distanz implementiert:
https://en.wikipedia.org/wiki/Levenshtein_distance
oder auch
https://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#C.2B.2B
-
Was musst du optimieren? Wie schnell darf das Preprocessing sein und wie schnell das Query? Es macht einen Unterschied ob es nur ein Query gibt oder mehrere.
-
Levenshtein Distanz wuerde das problem auch loesen jedoch ist die komplexitaet O(n*m) ...
