String-Kodierung, Umkehrung und Palindrome
Implementieren Sie die In-Place-Umkehrung von Wörtern, Run-Length-Encoding und die Palindromerkennung einschließlich der Technik zum Ausdehnen um die Mitte.
String-Kodierung, Umkehrung und Palindrome ist eine kostenlose DSA Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 4 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des DSA Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der DSA Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Einen String in-place umkehren
Python-Strings sind unveränderlich. Eine Umkehrung „in-place“ bedeutet daher, den String in eine Zeichenliste umzuwandeln, mithilfe zweier Zeiger Elemente zu vertauschen und die Liste anschließend wieder zusammenzufügen. Beim klassischen Tausch mit zwei Zeigern setzen Sie left auf den Index 0 und right auf den letzten Index. Vertauschen Sie die Zeichen und bewegen Sie die Zeiger nach innen, bis sie sich überkreuzen. Dies benötigt O(n) Zeit und O(n) Speicher für die Zeichenliste (unvermeidbar, da Strings unveränderlich sind).
def reverse_string(s):
chars = list(s)
left, right = 0, len(chars) - 1
while left < right:
chars[left], chars[right] = chars[right], chars[left]
left += 1
right -= 1
return ''.join(chars)
print(reverse_string('hello')) # 'olleh'
print(reverse_string('Hannah')) # 'hannaH'
# Pythonic shortcut (creates new string):
print('hello'[::-1]) # 'olleh'Wörter in einem Satz umkehren
Kehren Sie die Reihenfolge der Wörter um und entfernen Sie überflüssige Leerzeichen. Die klare Python-Lösung: split (verarbeitet mehrere Leerzeichen), kehrt die Liste um und verwendet join. Für eine Umkehrung in-place auf einem Zeichen-Array: Kehren Sie zuerst das gesamte Array um und anschließend jedes einzelne Wort. Dieser Ansatz mit zwei Durchläufen benötigt O(n) Zeit und O(n) Speicher (bei Python-Strings unvermeidbar, da sie unveränderlich sind).
def reverse_words(s):
words = s.split() # split and strip whitespace
words.reverse() # in-place reverse
return ' '.join(words) # single space between words
print(reverse_words(' hello world ')) # 'world hello'
print(reverse_words('a good example')) # 'example good a'
# One-liner:
print(' '.join(' hello world '.split()[::-1]))Einfache Palindromerkennung
Ein String ist ein Palindrom, wenn er mit seiner Umkehrung übereinstimmt. Die schnellste Prüfung in Python ist: s == s[::-1]. Für Palindrome, bei denen die Groß- und Kleinschreibung ignoriert wird und die nur alphanumerische Zeichen enthalten (die häufigste Variante in Vorstellungsgesprächen), normalisieren Sie den String zuerst: Filtern Sie nicht alphanumerische Zeichen heraus und wandeln Sie die übrigen in Kleinbuchstaben um. Vergleichen Sie anschließend beide Seiten. Beide Ansätze benötigen O(n).
def is_palindrome(s):
# Filter and normalise
cleaned = ''.join(c.lower() for c in s if c.isalnum())
return cleaned == cleaned[::-1]
print(is_palindrome('A man, a plan, a canal: Panama')) # True
print(is_palindrome('race a car')) # False
print(is_palindrome('Was it a car or a cat I saw?')) # TruePalindromerkennung mit zwei Zeigern
Um zusätzlichen Speicherplatz von O(1) zu verwenden, prüfen Sie das Palindrom mit zwei Zeigern statt durch Slicing. Setzen Sie left auf 0 und right auf das Ende. Überspringen Sie nicht alphanumerische Zeichen, vergleichen Sie die übrigen Zeichen ohne Beachtung der Groß- und Kleinschreibung und geben Sie bei einer Abweichung False zurück. Dieser Ansatz ist ausführlicher, vermeidet aber die vollständige Erstellung des bereinigten Strings – wichtig, wenn der Speicher begrenzt ist.
def is_palindrome_twoptr(s):
left, right = 0, len(s) - 1
while left < right:
while left < right and not s[left].isalnum():
left += 1
while left < right and not s[right].isalnum():
right -= 1
if s[left].lower() != s[right].lower():
return False
left += 1; right -= 1
return True
print(is_palindrome_twoptr('A man, a plan, a canal: Panama')) # TrueUm das Zentrum expandieren, um das längste Palindrom zu finden
Die Technik des Expandierens um das Zentrum findet den längsten palindromischen Teilstring in O(n²) Zeit und mit O(1) zusätzlichem Speicher. Expandieren Sie für jedes Zeichen (Palindrome ungerader Länge) und jede Lücke zwischen zwei Zeichen (Palindrome gerader Länge) nach außen, solange die Zeichen übereinstimmen. Speichern Sie das beste bisher gefundene Paar (start, end). Es gibt 2n-1 Zentren, und jede Expansion benötigt im schlimmsten Fall O(n).
def longest_palindrome(s):
best_start = best_end = 0
def expand(left, right):
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1; right += 1
return left + 1, right - 1 # last valid bounds
for i in range(len(s)):
l, r = expand(i, i) # odd-length
if r - l > best_end - best_start:
best_start, best_end = l, r
l, r = expand(i, i + 1) # even-length
if r - l > best_end - best_start:
best_start, best_end = l, r
return s[best_start:best_end+1]
print(longest_palindrome('babad')) # 'bab' or 'aba'
print(longest_palindrome('cbbd')) # 'bb'Vorschau auf Manachers Algorithmus
Manachers Algorithmus findet den längsten palindromischen Teilstring in O(n) Zeit. Dabei wird die Erkenntnis genutzt, dass ein Palindrom innerhalb eines größeren Palindroms anhand einer Spiegelposition initialisiert werden kann. In Vorstellungsgesprächen wird nur selten verlangt, den Algorithmus zu implementieren, aber es lohnt sich, seine Existenz zu kennen. Die meisten Interviewer akzeptieren den Ansatz des Expandierens um das Zentrum mit O(n²) als „ausreichend optimal“. Erwähnen Sie Manachers Algorithmus als theoretische O(n)-Lösung, wenn Sie nach einer weiterführenden Optimierung gefragt werden.
# Manacher's: O(n) longest palindromic substring
def manacher(s):
# Transform s into '#a#b#a#' to handle even/odd uniformly
t = '#' + '#'.join(s) + '#'
n = len(t)
P = [0] * n # P[i] = palindrome radius at i
center = right = 0
for i in range(n):
mirror = 2 * center - i
if i < right:
P[i] = min(right - i, P[mirror])
while (i + P[i] + 1 < n and i - P[i] - 1 >= 0
and t[i+P[i]+1] == t[i-P[i]-1]):
P[i] += 1
if i + P[i] > right:
center, right = i, i + P[i]
max_len = max(P)
center_idx = P.index(max_len)
start = (center_idx - max_len) // 2
return s[start:start+max_len]
print(manacher('babad')) # 'bab'Lauflängenkodierung
Lauflängenkodierung (RLE) komprimiert aufeinanderfolgende gleiche Zeichen: 'aaabbc' wird zu 'a3b2c1'. Implementierung: Durchlaufen Sie den String mit einem schnellen Zeiger, um das Ende jedes Laufs zu finden, schreiben Sie das Zeichen und seine Anzahl in eine Ausgabeliste und fügen Sie die Liste anschließend zusammen. Bei kurzen Läufen kann die Eingabe kürzer als die kodierte Ausgabe sein – prüfen Sie daher immer, ob die kodierte Version tatsächlich kürzer ist, bevor Sie sie zurückgeben.
def encode_rle(s):
if not s: return ''
parts = []
i = 0
while i < len(s):
char = s[i]
j = i
while j < len(s) and s[j] == char:
j += 1
count = j - i
parts.append(char + (str(count) if count > 1 else ''))
i = j
encoded = ''.join(parts)
return encoded if len(encoded) < len(s) else s
print(encode_rle('aaabbc')) # 'a3b2c'
print(encode_rle('abc')) # 'abc' (no compression gain)Lauflängenkodierte Strings dekodieren
Beim Dekodieren von RLE werden Zeichen und die jeweils folgenden Ziffernfolgen gelesen, um jeden Lauf zu erweitern. In Vorstellungsgesprächen wird manchmal die LeetCode-Variante verwendet, bei der die Kodierung k[encoded_string] für wiederholte Teilstrings nutzt: Beispielsweise wird 3[ab] zu ababab. Diese verschachtelte Variante benötigt einen Stack, um mehrere Verschachtelungsebenen zu verarbeiten.
def decode_rle(s):
result = []
i = 0
while i < len(s):
char = s[i]; i += 1
num_str = ''
while i < len(s) and s[i].isdigit():
num_str += s[i]; i += 1
count = int(num_str) if num_str else 1
result.append(char * count)
return ''.join(result)
print(decode_rle('a3b2c')) # 'aaabbc'
print(decode_rle('a2b3c1')) # 'aabbbc'
# Nested bracket decode (LeetCode 394)
def decode_bracket(s):
stack = []
for c in s:
if c != ']':
stack.append(c)
else:
chars = []
while stack[-1] != '[':
chars.append(stack.pop())
stack.pop() # remove '['
k = int(stack.pop())
stack.append(''.join(reversed(chars)) * k)
return ''.join(stack)
print(decode_bracket('3[ab]')) # 'ababab'Gültiges Palindrom II: Eine Löschung erlaubt
Gegeben sei ein String. Geben Sie True zurück, wenn Sie ihn durch das Löschen von höchstens einem Zeichen in ein Palindrom umwandeln können. Verwenden Sie zwei Zeiger. Prüfen Sie bei der ersten Abweichung, ob entweder s[left+1:right+1] oder s[left:right] ein Palindrom ist (überspringen Sie also jeweils eines der beiden abweichenden Zeichen). Wenn eine der beiden Seiten ein Palindrom ist, geben Sie True zurück. Dieser Greedy-Ansatz funktioniert, weil das Überspringen des abweichenden Zeichens die einzige sinnvolle Aktion ist.
def valid_palindrome(s):
def is_pal(l, r):
while l < r:
if s[l] != s[r]: return False
l += 1; r -= 1
return True
left, right = 0, len(s) - 1
while left < right:
if s[left] != s[right]:
# Try skipping either character
return is_pal(left+1, right) or is_pal(left, right-1)
left += 1; right -= 1
return True
print(valid_palindrome('aba')) # True
print(valid_palindrome('abca')) # True (delete 'c')
print(valid_palindrome('abc')) # FalsePalindrompartitionierung I
Teilen Sie einen String in alle Teilstrings auf, die Palindrome sind. Verwenden Sie Backtracking: Probieren Sie in jedem Schritt alle Präfixe des verbleibenden Strings aus. Ist ein Präfix ein Palindrom, wenden Sie den Algorithmus rekursiv auf den Rest an. Berechnen Sie mithilfe von Intervall-DP vorab eine zweidimensionale boolesche Tabelle is_pal[i][j], um Palindromprüfungen in O(1) zu ermöglichen. Dadurch reduziert sich der gesamte Aufwand des Backtrackings von O(n² × 2^n) auf O(n × 2^n) – akzeptabel, da das Erzeugen aller Partitionen von Natur aus exponentiell ist.
def partition(s):
n = len(s)
dp = [[False]*n for _ in range(n)]
for i in range(n):
dp[i][i] = True
for length in range(2, n+1):
for i in range(n-length+1):
j = i + length - 1
if s[i] == s[j]:
dp[i][j] = length == 2 or dp[i+1][j-1]
result = []
def backtrack(start, path):
if start == n: result.append(path[:]); return
for end in range(start, n):
if dp[start][end]:
path.append(s[start:end+1])
backtrack(end+1, path)
path.pop()
backtrack(0, [])
return result
print(partition('aab')) # [['a','a','b'],['aa','b']]Kürzestes Palindrom: String-Hashing
Finden Sie das kürzeste Palindrom, das entsteht, wenn Sie Zeichen am Anfang eines Strings hinzufügen. Die entscheidende Erkenntnis: Finden Sie das längste palindromische Präfix von s und stellen Sie die Umkehrung des verbleibenden Suffixes voran. Um das längste palindromische Präfix effizient zu finden, verwenden Sie die Failure-Funktion von KMP auf dem String s + '#' + reverse(s). Der letzte Wert der Failure-Funktion gibt die Länge des längsten palindromischen Präfixes an.
def shortest_palindrome(s):
rev = s[::-1]
combined = s + '#' + rev # '#' prevents overlap
n = len(combined)
kmp = [0] * n
j = 0
for i in range(1, n):
while j > 0 and combined[i] != combined[j]:
j = kmp[j-1]
if combined[i] == combined[j]:
j += 1
kmp[i] = j
# kmp[-1] = length of longest palindromic prefix
to_add = rev[:len(s) - kmp[-1]]
return to_add + s
print(shortest_palindrome('aacecaaa')) # 'aaacecaaa'
print(shortest_palindrome('abcd')) # 'dcbabcd'Schnelltest
Überprüfen Sie Ihr Verständnis der Konzepte aus dieser Lektion zu Data Structures & Algorithms — Coding Interview Prep.
Zusammenfassung der Lektion
In dieser Lektion haben Sie gelernt: Die Palindromerkennung mit zwei Zeigern benötigt O(n) Zeit und O(1) Speicher – verwenden Sie bei begrenztem Speicher immer indexbasierte Prüfungen, statt eine umgekehrte Kopie zu erstellen, das Expandieren um das Zentrum findet den längsten palindromischen Teilstring in O(n²), indem jede der 2n-1 Positionen als potenzielles Palindromzentrum betrachtet wird, und die Lauflängenkodierung komprimiert aufeinanderfolgende Läufe in O(n), während das Dekodieren der verschachtelten Variante mit eckigen Klammern einen Stack erfordert. Als Nächstes sehen wir uns Bubble Sort und Insertion Sort an.
Lerne Python mit einem KI-Tutor — kostenlos
Schreibe und führe echten Code in deinem Browser aus, bekomme sofortige Hilfe von einem 24/7 KI-Tutor und setze dein Lernen im Web oder in der App fort.
- Kurse
- 30
- Lektionen
- 120
Häufig gestellte Fragen
Ist die Lektion „String-Kodierung, Umkehrung und Palindrome“ kostenlos?
Ja — der vollständige Text von „String-Kodierung, Umkehrung und Palindrome“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des DSA Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der DSA Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „String-Kodierung, Umkehrung und Palindrome“?
Implementieren Sie die In-Place-Umkehrung von Wörtern, Run-Length-Encoding und die Palindromerkennung einschließlich der Technik zum Ausdehnen um die Mitte. Du übst DSA Interview Prep mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um DSA Interview Prep zu starten?
Keine Vorkenntnisse erforderlich. DSA Interview Prep auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 4 von 4.
Wie lange dauert die Lektion „String-Kodierung, Umkehrung und Palindrome“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser DSA Interview Prep-Lektion Code schreiben und ausführen?
Ja. Jede DSA Interview Prep-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- Python-String-API für Interviews
- Sliding Window für Teilstrings
- Anagramme und Zeichenhäufigkeitskarten
- String-Kodierung, Umkehrung und Palindrome