Stringcodering, omkeren en palindromen
Implementeer het in-place omkeren van woorden, run-length encoding en palindroomdetectie, inclusief de techniek expand-around-centre.
Stringcodering, omkeren en palindromen is een gratis DSA Interview Prep-les op CoddyKit. Dit is les 4 van 4. Je kunt 3 lessen uit dit leerpad gratis volledig lezen — daarna ontgrendelt CoddyKit PRO alle lessen, plus praktische oefeningen met een ingebouwde code-editor en een AI-tutor die 24/7 beschikbaar is. Deze les maakt deel uit van het leertraject DSA Interview Prep. Je voortgang wordt gesynchroniseerd op het web en in de CoddyKit-app. De cursus DSA Interview Prep bevat in totaal 4 lessen.
Een tekenreeks ter plaatse omkeren
Python-tekenreeksen zijn onveranderlijk, dus 'ter plaatse' omkeren betekent dat je de tekenreeks omzet in een tekenlijst, met twee aanwijzers verwisselt en de lijst weer samenvoegt. Bij de klassieke verwisseling met twee aanwijzers plaats je left op index 0 en right op de laatste index; verwissel tekens en beweeg de aanwijzers naar elkaar toe totdat ze elkaar kruisen. Dit kost O(n) tijd en O(n) ruimte voor de tekenlijst (onvermijdelijk omdat tekenreeksen onveranderlijk zijn).
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'Woorden in een zin omkeren
Keer de volgorde van de woorden om en verwijder overtollige spaties. De overzichtelijke Python-oplossing: splitsen (werkt ook bij meerdere spaties), de lijst omkeren en samenvoegen. Voor ter plaatse omkeren in een tekenarray: keer eerst de hele array om en keer daarna elk afzonderlijk woord om. Deze aanpak met twee doorgangen kost O(n) tijd en O(n) ruimte (onvermijdelijk bij Python-tekenreeksen omdat ze onveranderlijk zijn).
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]))Palindroomdetectie: eenvoudig
Een tekenreeks is een palindroom als deze gelijk is aan de omgekeerde tekenreeks. De snelste controle in Python: s == s[::-1]. Voor palindromen zonder onderscheid tussen hoofdletters en kleine letters die alleen uit letters en cijfers bestaan (de meest voorkomende variant bij sollicitatiegesprekken), normaliseer je de tekenreeks eerst: filter niet-alfanumerieke tekens weg en zet de rest om naar kleine letters, en vergelijk daarna de tekenreeksen. Beide aanpakken kosten 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?')) # TruePalindroomdetectie: twee aanwijzers
Gebruik voor O(1) extra ruimte twee aanwijzers in plaats van een omgekeerde kopie te maken. Plaats left op 0 en right aan het einde. Sla niet-alfanumerieke tekens over, vergelijk de overige tekens zonder onderscheid tussen hoofdletters en kleine letters en geef False terug zodra ze verschillen. Deze aanpak is uitvoeriger, maar voorkomt dat je überhaupt de opgeschoonde tekenreeks maakt — belangrijk wanneer het geheugen beperkt is.
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')) # TrueRond het middelpunt uitbreiden voor het langste palindroom
Met de techniek om rond het middelpunt uit te breiden vind je de langste palindromische deeltekenreeks in O(n²) tijd met O(1) extra ruimte. Breid voor elk teken (palindromen met een oneven lengte) en elke opening tussen tekens (palindromen met een even lengte) naar buiten uit zolang de tekens overeenkomen. Houd het beste paar (start, einde) bij dat je tegenkomt. Er zijn 2n-1 middelpunten en elke uitbreiding kost in het slechtste geval 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'Vooruitblik op het algoritme van Manacher
Het algoritme van Manacher vindt de langste palindromische deeltekenreeks in O(n) tijd. Het gebruikt daarbij het inzicht dat je een palindroom binnen een groter palindroom kunt initialiseren vanuit een spiegelpositie. Bij sollicitatiegesprekken wordt zelden gevraagd om dit algoritme te implementeren, maar het is de moeite waard om te weten dat het bestaat. De meeste interviewers accepteren de aanpak waarbij je rond het middelpunt uitbreidt in O(n²) als 'optimaal genoeg' — noem Manachers algoritme als de theoretische O(n)-oplossing wanneer er een vervolgvraag komt.
# 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'Runlengtecodering
Runlengtecodering (RLE) comprimeert opeenvolgende herhaalde tekens: 'aaabbc' wordt 'a3b2c1'. Implementatie: doorloop de tekenreeks met een snelle aanwijzer om het einde van elke reeks te vinden, schrijf het teken en de lengte naar een uitvoerlijst en voeg de lijst daarna samen. De invoer kan bij korte reeksen korter zijn dan de gecodeerde uitvoer — controleer altijd of de gecodeerde versie korter is voordat je deze teruggeeft.
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)Runlengtegecodeerde tekenreeksen decoderen
Bij het decoderen van RLE lees je tekens en de daaropvolgende reeksen cijfers en breid je elke reeks uit. Interviewers gebruiken soms de LeetCode-variant waarin de codering k[encoded_string] gebruikt voor herhaalde deeltekenreeksen: bijvoorbeeld 3[ab] → ababab. Voor deze geneste variant heb je een stapel nodig om meerdere niveaus van nesten te verwerken.
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'Geldig palindroom II: één verwijdering toegestaan
Geef voor een tekenreeks True terug als je er door hoogstens één teken te verwijderen een palindroom van kunt maken. Gebruik twee aanwijzers; controleer bij het eerste verschil of s[left+1:right+1] of s[left:right] een palindroom is (probeer dus elk van de twee verschillende tekens over te slaan). Geef True terug als een van beide kanten een palindroom is. Deze gretige aanpak werkt omdat het overslaan van een van de verschillende tekens de enige nuttige actie is.
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')) # FalsePalindroompartitionering I
Verdeel een tekenreeks in alle deeltekenreeksen die palindromen zijn. Gebruik backtracking: probeer bij elke stap alle voorvoegsels van de resterende tekenreeks; als een voorvoegsel een palindroom is, roep je de aanpak recursief aan voor de rest. Bereken vooraf een tweedimensionale booleaanse tabel is_pal[i][j] met interval-DP om palindroomcontroles O(1) te maken. Daarmee verlaag je de totale backtracking van O(n² × 2^n) naar O(n × 2^n) — acceptabel omdat het genereren van alle partitioneringen van nature exponentieel is.
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']]Kortste palindroom: tekenreeks hashen
Vind het kortste palindroom dat je kunt krijgen door tekens aan het begin van een tekenreeks toe te voegen. Het belangrijkste inzicht: vind het langste palindromische voorvoegsel van s en voeg daarna de omgekeerde versie van het resterende achtervoegsel ervoor. Gebruik de foutfunctie van KMP op de tekenreeks s + '#' + reverse(s) om het langste palindromische voorvoegsel efficiënt te vinden. De laatste waarde van de foutfunctie geeft de lengte van het langste palindromische voorvoegsel.
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'Korte controle
Controleer je begrip van de concepten uit deze les van Data Structures & Algorithms — Coding Interview Prep.
Samenvatting van de les
In deze les heb je geleerd: palindroomdetectie met twee aanwijzers kost O(n) tijd en O(1) ruimte — geef altijd de voorkeur aan controles op basis van indexen boven het toewijzen van een omgekeerde kopie wanneer ruimte belangrijk is, uitbreiden rond het middelpunt vindt de langste palindromische deeltekenreeks in O(n²) door elk van de 2n-1 posities als mogelijk palindroommiddelpunt te behandelen, en runlengtecodering comprimeert opeenvolgende reeksen in O(n), terwijl voor het decoderen van de geneste variant met haakjes een stapel nodig is. Hierna behandelen we bubblesort en invoegsortering.
Leer Python met een AI-tutor — gratis
Schrijf echte code en voer die uit in je browser, krijg direct hulp van een AI-tutor die 24/7 beschikbaar is en ga verder waar je gebleven bent op het web of in de app.
- Cursussen
- 30
- Lessen
- 120
Veelgestelde vragen
Is de les “Stringcodering, omkeren en palindromen” gratis?
Ja — je kunt hier op het web alle 3 lessen van het leerpad DSA Interview Prep, waaronder “Stringcodering, omkeren en palindromen”, gratis volledig lezen. Daarna ontgrendelt CoddyKit PRO alle lessen, plus interactieve oefeningen met een ingebouwde code-editor en een AI-tutor die 24/7 beschikbaar is. De cursus DSA Interview Prep bevat in totaal 4 lessen.
Wat leer ik in “Stringcodering, omkeren en palindromen”?
Implementeer het in-place omkeren van woorden, run-length encoding en palindroomdetectie, inclusief de techniek expand-around-centre. Je oefent met DSA Interview Prep door code rechtstreeks in de browser uit te voeren. Een AI-begeleider die 24/7 beschikbaar is beantwoordt je vragen terwijl je de les doorwerkt.
Heb ik ervaring nodig om met DSA Interview Prep te beginnen?
Ervaring vooraf is niet nodig. DSA Interview Prep op CoddyKit is opgebouwd voor beginners tot gevorderden, zodat je hier of bij het begin kunt starten en in je eigen tempo kunt leren. Dit is les 4 van 4.
Hoe lang duurt de les “Stringcodering, omkeren en palindromen”?
De meeste lessen van CoddyKit duren ongeveer 5–10 minuten. Elke les is kort en interactief, zodat je gestaag vooruitgaat en op het web en in de app precies verdergaat waar je was gebleven.
Kan ik code schrijven en uitvoeren in deze les over DSA Interview Prep?
Ja. Elke les over DSA Interview Prep bevat een ingebouwde code-editor, zodat je rechtstreeks in je browser echte code kunt schrijven en uitvoeren en direct feedback van AI krijgt — lokale installatie is niet nodig.
Alle lessen in deze cursus
- Python String API voor interviews
- Sliding window voor substrings
- Anagrammen en frequentiemaps voor tekens
- Stringcodering, omkeren en palindromen