Ein Palindrom ist ein String, eine Zahl oder eine Sequenz, die vorwärts und rückwärts gleich gelesen wird.
Beispiele:
racecar
level
madam
1221
Nicht-palindromische Beispiele sind:
hello
algorithm
1234
Die Aufgabe ist besonders nützlich, um die Technik Two Pointers zu lernen.
Lösung durch Umkehren
Eine einfache Lösung erzeugt einen umgekehrten String:
function isPalindrome(value: string): boolean {
return value === value.split("").reverse().join("");
}
Komplexität:
Time: O(n)
Space: O(n)
Two Pointers
Effizienter ist es, zwei Pointer an beiden Enden zu platzieren.
r a c e c a r
↑ ↑
L R
Sind beide Zeichen gleich, bewegen sich die Pointer zur Mitte.
function isPalindrome(value: string): boolean {
let left = 0;
let right = value.length - 1;
while (left < right) {
if (value[left] !== value[right]) {
return false;
}
left++;
right--;
}
return true;
}
Damit erhalten wir:
Time: O(n)
Space: O(1)
Leerzeichen und Satzzeichen ignorieren
Ein klassisches Beispiel lautet:
A man, a plan, a canal: Panama
Nach Normalisierung ergibt sich:
amanaplanacanalpanama
und der Text ist ein Palindrom.
In einer speichereffizienten Lösung können nicht-alphanumerische Zeichen direkt beim Bewegen der Pointer übersprungen werden.
Zahlen als Palindrome
Auch Zahlen können Palindrome sein:
121
1221
4554
Eine Möglichkeit besteht darin, die Zahl als String zu prüfen. Alternativ kann die Zahl mathematisch umgekehrt werden.
function isNumberPalindrome(value: number): boolean {
if (value < 0) return false;
const original = value;
let reversed = 0;
while (value > 0) {
const digit = value % 10;
reversed = reversed * 10 + digit;
value = Math.floor(value / 10);
}
return original === reversed;
}
Rekursive Variante
Man kann jeweils das erste und letzte Zeichen prüfen und anschließend rekursiv den inneren Bereich untersuchen.
Die Laufzeit bleibt O(n), allerdings benötigt der Call Stack zusätzlichen Speicher von ungefähr O(n).
Almost Palindrome
Eine häufige Erweiterung lautet:
Kann der String durch das Entfernen höchstens eines Zeichens zu einem Palindrom werden?
Bei einem ersten Mismatch kann man prüfen, ob das Überspringen des linken oder rechten Zeichens eine gültige Lösung liefert.
Verwandte Probleme
Die gleiche Grundidee erscheint bei:
- Longest Palindromic Substring
- Palindromic Subsequence
- Palindrome Partitioning
- Valid Palindrome
- Minimum Insertions
Two Pointers als allgemeines Muster
Two Pointers wird nicht nur für Palindrome verwendet, sondern auch bei:
- Pair Sum
- Remove Duplicates
- Partitioning
- Array Merge
- Container With Most Water
Das Palindromproblem ist deshalb ein guter Einstieg in dieses Algorithmusmuster.
Groß- und Kleinschreibung
Ob Level als Palindrom gilt, hängt von der Definition ab.
Case-sensitive ist L ungleich l. Nach Umwandlung in lowercase ergibt sich level.
Typische Interviewaufgabe
Häufig sollen Leerzeichen, Satzzeichen und Groß-/Kleinschreibung ignoriert werden.
Ein guter Ansatz kombiniert:
Two Pointers
Skip non-alphanumeric characters
Case-insensitive comparison
und erreicht:
Time: O(n)
Space: O(1)
Edge Cases
"" → true
"a" → true
"aa" → true
"ab" → false
"racecar" → true
Fazit
Ein Palindrom ist von beiden Seiten identisch lesbar.
Die typische algorithmische Lösung verwendet Two Pointers mit:
Time Complexity: O(n)
Space Complexity: O(1)
Das Problem ist besonders wertvoll, weil es symmetrisches Denken, Edge Cases und eine der wichtigsten Pointer-Techniken vermittelt.