Algorithmen und Datenstrukturen · Junior · Frage 43 von 75
Wie prüft man in O(n) Zeit und O(1) zusätzlichem Speicher, ob ein String ein Palindrom ist?
- 1Die Zeichen sortieren und mit dem Original vergleichen
- 2Zeichen von beiden Enden zur Mitte hin vergleichen
- 3Den String mit
str.split("").reverse().join("")vergleichen
Antwort zeigen
Richtige Antwort: Zeichen von beiden Enden zur Mitte hin vergleichen
Erklärung
Zwei Zeiger vergleichen s[i] mit s[j] und stoppen bei der ersten Abweichung. Umdrehen funktioniert auch, erzeugt aber einen neuen String und braucht O(n) Speicher. Sortieren ist falsch: es verliert die Reihenfolge der Zeichen.