Codifica, inversione e palindromi delle stringhe
Implementi l'inversione in-place delle parole, la codifica run-length e il rilevamento dei palindromi, inclusa la tecnica expand-around-centre
Codifica, inversione e palindromi delle stringhe è una lezione Coding Interview Prep gratuita su CoddyKit. Questa è la lezione 4 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Coding Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Coding Interview Prep include 4 lezioni in totale.
Inversione di una stringa in-place
Le stringhe Python sono immutabili, quindi l'inversione in-place consiste nel convertirle in una lista di caratteri, effettuare lo scambio con due puntatori e ricomporre la stringa. Nel classico scambio con due puntatori, si posiziona left all'indice 0 e right sull'ultimo indice; si scambiano i caratteri e si spostano i puntatori verso il centro finché non si incrociano. Il tempo è O(n) e lo spazio è O(n) per la lista di caratteri (inevitabile, poiché le stringhe sono immutabili).
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'Inversione dell'ordine delle parole in una frase
Inverta l'ordine delle parole eliminando gli spazi superflui. La soluzione Python più pulita consiste nell'usare split (che gestisce più spazi), invertire la lista e usare join. Per l'inversione in-place di un array di caratteri, inverta prima l'intero array e poi ogni singola parola. Questo approccio in due passaggi ha un tempo O(n) e uno spazio O(n) (inevitabile con le stringhe Python, poiché sono immutabili).
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]))Rilevamento dei palindromi: metodo semplice
Una stringa è un palindromo se è uguale alla propria inversione. Il controllo Python più rapido è s == s[::-1]. Per i palindromi senza distinzione tra maiuscole e minuscole e contenenti solo caratteri alfanumerici (la variante più comune nei colloqui tecnici), normalizzi prima la stringa: filtri i caratteri non alfanumerici e converti tutto in minuscolo, quindi confronti. Entrambi gli approcci hanno complessità 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?')) # TrueRilevamento dei palindromi: due puntatori
Per usare uno spazio aggiuntivo O(1), verifichi se la stringa è un palindromo con due puntatori anziché tramite slicing. Posizioni left su 0 e right alla fine. Salti i caratteri non alfanumerici, confronti senza distinzione tra maiuscole e minuscole i caratteri rimanenti e restituisca False in caso di differenza. È più verboso, ma evita di creare completamente la stringa ripulita, un aspetto importante quando la memoria è limitata.
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')) # TrueEspansione dal centro per il palindromo più lungo
La tecnica dell'espansione dal centro trova la sottostringa palindroma più lunga in un tempo O(n²) e con uno spazio aggiuntivo O(1). Per ogni carattere (palindromi di lunghezza dispari) e per ogni spazio tra caratteri (palindromi di lunghezza pari), si espande verso l'esterno finché i caratteri corrispondono. Si tiene traccia della migliore coppia (start, end) incontrata. I centri possibili sono 2n-1 e ogni espansione richiede O(n) nel caso peggiore.
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'Panoramica dell'algoritmo di Manacher
L'algoritmo di Manacher trova la sottostringa palindroma più lunga in tempo O(n), sfruttando l'idea che un palindromo contenuto in un palindromo più grande può essere inizializzato a partire da una posizione speculare. Nei colloqui tecnici viene raramente richiesto di implementarlo, ma vale la pena sapere che esiste. La maggior parte degli intervistatori considera l'approccio dell'espansione dal centro in O(n²) «abbastanza ottimale»: se viene richiesta un'ulteriore soluzione, citi Manacher come soluzione teorica in O(n).
# 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'Codifica run-length
La codifica run-length (RLE) comprime i caratteri ripetuti consecutivamente: 'aaabbc' diventa 'a3b2c1'. L'implementazione scorre la stringa con un puntatore rapido per trovare la fine di ogni run, scrive il carattere e il conteggio in una lista di output, quindi concatena gli elementi. L'input può essere più corto dell'output codificato per i run brevi: verifichi sempre che la versione codificata sia più corta prima di restituirla.
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)Decodifica di stringhe codificate con run-length
La decodifica RLE legge i caratteri e le sequenze di cifre che li seguono, espandendo ogni run. Talvolta gli intervistatori presentano la variante di LeetCode in cui la codifica usa k[encoded_string] per ripetere le sottostringhe: ad esempio, 3[ab] → ababab. Questa variante annidata richiede uno stack per gestire più livelli di annidamento.
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'Palindromo valido II: è consentita una cancellazione
Data una stringa, restituisca True se è possibile trasformarla in un palindromo eliminando al massimo un carattere. Utilizzi due puntatori; alla prima differenza, verifichi se s[left+1:right+1] o s[left:right] è un palindromo (ovvero provi a saltare ciascuno dei due caratteri diversi). Se uno dei due lati è un palindromo, restituisca True. Questo approccio greedy funziona perché saltare il carattere diverso è l'unica azione utile.
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')) # FalsePartizionamento in palindromi I
Suddivida una stringa in tutte le sottostringhe palindrome possibili. Utilizzi il backtracking: a ogni passaggio, provi tutti i prefissi della parte restante della stringa; se un prefisso è un palindromo, richiami ricorsivamente l'algoritmo sul resto. Precalcoli una tabella booleana bidimensionale is_pal[i][j] usando la programmazione dinamica sugli intervalli, in modo da rendere O(1) i controlli dei palindromi e ridurre il backtracking complessivo da O(n² × 2^n) a O(n × 2^n), un risultato accettabile poiché la generazione di tutte le partizioni è per natura esponenziale.
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']]Palindromo più breve: hashing di stringhe
Trovi il palindromo più breve ottenibile aggiungendo caratteri all'inizio di una stringa. L'idea chiave consiste nel trovare il prefisso palindromo più lungo di s, quindi anteporre l'inversione del suffisso rimanente. Per trovare in modo efficiente il prefisso palindromo più lungo, utilizzi la funzione di fallimento di KMP sulla stringa s + '#' + reverse(s). L'ultimo valore della funzione di fallimento indica la lunghezza del prefisso palindromo più lungo.
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'Verifica rapida
Verifichi la Sua comprensione dei concetti di Data Structures & Algorithms — Coding Interview Prep trattati in questa lezione.
Riepilogo della lezione
In questa lezione ha imparato che: il rilevamento dei palindromi con due puntatori richiede tempo O(n) e spazio O(1): quando lo spazio è importante, preferisca sempre i controlli basati sugli indici alla creazione di una copia invertita; l'espansione dal centro trova la sottostringa palindroma più lunga in O(n²), considerando ciascuna delle 2n-1 posizioni come un possibile centro del palindromo; e la codifica run-length comprime i run consecutivi in O(n), mentre la decodifica richiede uno stack per la variante annidata con parentesi quadre. Prossimamente esamineremo bubble sort e insertion sort.
Domande Frequenti
La lezione «Codifica, inversione e palindromi delle stringhe» è gratuita?
Sì — il testo completo di «Codifica, inversione e palindromi delle stringhe» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Coding Interview Prep, passa a CoddyKit PRO. Il corso Coding Interview Prep include 4 lezioni in totale.
Cosa imparerò in «Codifica, inversione e palindromi delle stringhe»?
Implementi l'inversione in-place delle parole, la codifica run-length e il rilevamento dei palindromi, inclusa la tecnica expand-around-centre Eserciti Coding Interview Prep con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare Coding Interview Prep?
Non è richiesta alcuna esperienza precedente. Coding Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 4 di 4.
Quanto tempo richiede la lezione «Codifica, inversione e palindromi delle stringhe»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione Coding Interview Prep?
Sì. Ogni lezione Coding Interview Prep include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- API delle stringhe Python per i colloqui
- Sliding window per le sottostringhe
- Anagrammi e mappe delle frequenze dei caratteri
- Codifica, inversione e palindromi delle stringhe