C++ palindrom testen?
Mein Ansatz hier ist folgender:
Testen ob der String gerade ist, falls ja:
String in der hälfte splitten, und die beiden dann vergleichen.
Falls der String ungerade ist:
String ein Char vor der mitte splitten (str1hold). dann testen ob str1hold gleich ist mit der anderen hälfte vom inputString.
also for (int a = (inputString.length() / 2) + 1; a < inputString.length(); a++)
aber das ganze ist doch ziemlich blöd finde ich, hat einer einen besseren ansatz?
4 Antworten
Wenn ich das richtig verstanden habe, geht es dir um eine Lösung in C++, oder?
Die anderen Antworten sind auch OK, aber eine "Konvertierung" in ein char-Array, bzw. ein Zeiger auf den internen Puffer, kannst du dir sparen, da ::std::string den operator[]() überlädt.
Außerdem kann dir egal sein, ob die Länge gerade oder ungerade ist, da die Länge eine Ganzahl ist, und bei einer Division durch Zwei der Rest sowieso verworfen wird, was du in einer Schleife ganz gut ausnutzen kannst:
#include <string>
#include <cstdlib> // size_t
// ...
bool is_palindrome(const ::std::string & str) noexcept {
if (str.empty()) {
return false;
}
for (size_t l = 0, r = str.size() - 1; l < r; ++l, --r) {
if (str[l] != str[r]) {
return false;
}
}
return true;
}
Wie du siehst, brauchst du eigentlich nur zwei Indizes, mit denen du einmal von links, und einmal von rechts zählst. Es geht allerdings auch mit nur einem Index und die Prüfung auf einen leeren String am Anfang kannst du mit leicht abgewandeltem Ansatz auch weg lassen.
Außerdem kannst du das ja noch beliebig ausbauen, sodass Groß- und Kleinschreibung keine Rolle mehr spielen, und "Leseesel" als Palindrom erkannt wird, obwohl sich das erste und das letzte "Ell" unterscheiden. Aber danach hast du ja nicht gefragt ... :)
Falls du mit obiger schleife Verständnisprobleme hast, steppe mal schrittweise mit einem Debugger durch, oder gehe die einzelnen Schritte auf einem Blatt Papier durch.
Viel Spaß! :)
PS: Du kannst auch eine schön kurze Lösung mit dem <algorithm> Header der STL haben:
#include <algorithm> // equal
#include <string>
// ...
bool is_palindrome(const ::std::string & s) noexcept {
using namespace std;
return s.size() && equal(s.cbegin(), s.cend(), s.crbegin());
}
Das ist aber etwas ineffizient, da der String "doppelt" geprüft wird. Effizienter, aber weniger schön, geht das ganze so:
#include <algorithm> // equal
#include <string>
#include <cstdlib> // size_t
// ...
bool is_palindrome(const ::std::string & s) noexcept {
using namespace std;
const size_t len = s.size();
return len && equal(s.cbegin(), s.cbegin() + len / 2, s.crbegin());
}
So ähnlich sieht auch die Lösung in der C++ Referenz aus (allerdings liefert diese bei Leerstrings "true" zurück):
Ehm, eigentlich würdest Du am Anfang vom String beginnen, bis Länge/2 laufen lassen und die aktuelle Position mit Länge-aktuelle Position-1 vergleichen.
Alternativ nimmt man Iteratoren und überlegt sich jetzt nur noch, wie die Abbruchbedingung aussehen müßte.
Alles was du benötigst, ist eine Schleife und eine Überprüfung pro Iteration, ob es stets gleiche Zeichenpaare gibt. Den String zerlegst du zuvor am besten in ein Array aus Characters.
Pseudocode:
char letters[] = /* ... */;
for i = 0, j = wordlength - 1; i < wordlength / 2; ++i, --j
if toLower(letters[i]) != toLower(letters[j])
return 0
return 1
Wenn das Wort nur einen einzigen Buchstaben beinhaltet, kannst du dir die Schleife sparen und gleich ein positives Ergebnis zurückgeben.
- String A in chars splitten
- chars in ein char[] array packen
- array rückwärts durch loopen und in jeder schleife die chars zu einem String B concaternaten
- if(B.equals(A)){ //palindrom}
alter, das ist ein Funktionsaufruf und eine Schleife. das ist ein 5 Zeiler...
Das ist aber arg umständlich und ein char array benötigt man auch nicht wirklich.
eine Schleife durchlaufen find ich jetzt nicht wirklich umständlich
9 von 10 Tests mit verschiedenem Input werden bestanden.
Nur bei einem bekomme ich einen ganz komischen output. dieser ist weder der kürzeste, noch der längste string von den Tests. daher kann ich mir garnicht erklären, warum ausgerechnet der nicht funktioniert.
Input = "abacaba" output = "abacaba {r��*"
Kann es mir nicht erklären. https://pastebin.com/Sun61MKF
@Karl @reg, eure lösung werde ich gleich auch versuchen, vorher will ich aber herausfinden, warum meine aktuelle lösung nicht funktioniert.
Es geht um den Umweg über das char array. Wenn man schon einen String hat, nennen wir ihn mal s, und in mit seinem 'Inversen' vergleichen möchte, dann ist das in C++ ein Einzeiler:
s==std::string(s.crbegin(), s.crend())
Der Ausdruck ist wahr, sofern s ein Palindrom enthält. Allerdings ist diese Variante naturgemäß langsamer, als via Schleife nur den halben String abzuwandern.
das bringt leider nichts, weil es lediglich um den return wert geht. die ausgabe habe ich nur zum testen eingefügt. es muss irgendwas in der For schleife falsch laufen.
hier mal ein bild zum besseren Verständnis:
Ja logisch, Dein array muß Stringlänge+1 haben und am Ende muß ein \0 stehen, damit es ein korrekt terminierter c-String ist, von dem Du dann ein std::string instanziieren kannst.
http://www.cplusplus.com/reference/string/string/string/
Siehe Konstruktorvariante (4)
Danke dir! habe das array um eins erweitert, und nach der for schleife die abschluss 0 hinzugefügt. Funktioniert jetzt perfekt. Werde mich nun mal an deinen bzw regex vorschlag setzen.
danke, werd ich gleich mal ausprobieren und schaun ob es im zeitlimit ist.
Das klingt ja katastrophal. Es wurde nicht danach gefragt, ein Palindrom auf die möglichst maximal ineffiziente Weise zu finden. :)