Codage, inversion et palindromes de chaînes
Implémentez l’inversion de mots en place, le codage par plages et la détection de palindromes, notamment la technique d’expansion autour du centre.
Codage, inversion et palindromes de chaînes est une leçon Coding Interview Prep gratuite sur CoddyKit. Ceci est la leçon 4 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Coding Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Coding Interview Prep comprend 4 leçons au total.
Inverser une chaîne en place
Les chaînes de caractères Python sont immuables ; l’inversion « en place » consiste donc à les convertir en liste de caractères, à effectuer des échanges avec deux pointeurs, puis à utiliser join. Échange classique avec deux pointeurs : placez left à l’index 0 et right au dernier index ; échangez les caractères et rapprochez les pointeurs jusqu’à ce qu’ils se croisent. Cela s’exécute en O(n) et nécessite O(n) d’espace pour la liste de caractères (inévitable puisque les chaînes sont immuables).
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'Inverser les mots d’une phrase
Inversez l’ordre des mots en supprimant les espaces superflus. Solution Python claire : utilisez split (qui gère les espaces multiples), inversez la liste, puis utilisez join. Pour inverser en place un tableau de caractères : inversez tout le tableau, puis inversez chaque mot individuellement. Cette approche en deux passes s’exécute en O(n) et utilise O(n) d’espace (inévitable avec les chaînes Python, puisqu’elles sont immuables).
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]))Détection simple des palindromes
Une chaîne est un palindrome si elle est égale à son inverse. La vérification Python la plus rapide : s == s[::-1]. Pour les palindromes composés uniquement de caractères alphanumériques et sans distinction de casse (la variante d’entretien la plus courante), normalisez d’abord la chaîne : filtrez les caractères non alphanumériques et convertissez-la en minuscules, puis comparez. Les deux approches s’exécutent en 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?')) # TrueDétection des palindromes avec deux pointeurs
Pour utiliser O(1) d’espace supplémentaire, vérifiez si la chaîne est un palindrome avec deux pointeurs plutôt qu’avec une tranche. Placez left à 0 et right à la fin. Ignorez les caractères non alphanumériques, comparez les caractères restants sans distinction de casse et renvoyez False en cas de différence. Cette méthode est plus verbeuse, mais elle évite de créer entièrement la chaîne nettoyée — ce qui est important lorsque la mémoire est limitée.
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')) # TrueExpansion autour du centre pour trouver le plus long palindrome
La technique de l’expansion autour du centre trouve la plus longue sous-chaîne palindromique en O(n²) avec O(1) d’espace supplémentaire. Pour chaque caractère (palindromes de longueur impaire) et chaque intervalle entre deux caractères (palindromes de longueur paire), étendez l’intervalle vers l’extérieur tant que les caractères correspondent. Conservez la meilleure paire (début, fin) rencontrée. Il existe 2n-1 centres et chaque expansion s’effectue en O(n) dans le pire cas.
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'Aperçu de l’algorithme de Manacher
L’algorithme de Manacher trouve la plus longue sous-chaîne palindromique en O(n), grâce à l’idée qu’un palindrome contenu dans un palindrome plus grand peut être initialisé à partir d’une position miroir. Il est rarement demandé de l’implémenter lors des entretiens, mais il est utile de savoir qu’il existe. La plupart des examinateurs acceptent l’approche de l’expansion autour du centre en O(n²) comme « suffisamment optimale » — mentionnez Manacher comme solution théorique en O(n) si l’on vous demande un approfondissement.
# 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'Codage par longueurs de séquences
Le codage par longueurs de séquences (RLE) compresse les suites de caractères répétés consécutivement : 'aaabbc' devient 'a3b2c1'. Pour l’implémenter, parcourez la chaîne avec un pointeur rapide afin de trouver la fin de chaque séquence, écrivez le caractère et le nombre d’occurrences dans une liste de sortie, puis utilisez join. L’entrée peut être plus courte que la sortie encodée pour les séquences courtes — vérifiez toujours que la version encodée est plus courte avant de la renvoyer.
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)Décoder des chaînes encodées par longueurs de séquences
Le décodage de RLE lit les caractères et les suites de chiffres qui les suivent, puis développe chaque séquence. Les examinateurs présentent parfois la variante de LeetCode dans laquelle l’encodage utilise k[encoded_string] pour répéter des sous-chaînes : par exemple, 3[ab] → ababab. Cette variante imbriquée nécessite une pile pour gérer plusieurs niveaux d’imbrication.
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'Palindrome valide II : une suppression autorisée
Étant donné une chaîne, renvoyez True si vous pouvez en faire un palindrome en supprimant au plus un caractère. Utilisez deux pointeurs ; lors du premier désaccord, vérifiez si s[left+1:right+1] ou s[left:right] est un palindrome (autrement dit, essayez d’ignorer chacun des caractères en désaccord). Si l’un des deux côtés est un palindrome, renvoyez True. Cette approche gloutonne fonctionne, car ignorer le caractère en désaccord est la seule action 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')) # FalsePartitionnement en palindromes I
Découpez une chaîne en toutes les sous-chaînes qui sont des palindromes. Utilisez le retour sur trace : à chaque étape, essayez tous les préfixes de la chaîne restante ; si un préfixe est un palindrome, appliquez récursivement la même méthode au reste. Pré-calculer un tableau booléen 2D is_pal[i][j] à l’aide de la programmation dynamique par intervalles (DP) permet de rendre les vérifications de palindrome O(1), ce qui réduit le coût global du retour sur trace de O(n² × 2^n) à O(n × 2^n) — un coût acceptable puisque la génération de toutes les partitions est de nature exponentielle.
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']]Palindrome le plus court : hachage de chaîne
Trouvez le palindrome le plus court que l’on puisse obtenir en ajoutant des caractères au début d’une chaîne. L’idée essentielle consiste à trouver le plus long préfixe palindromique de s, puis à ajouter au début l’inverse du suffixe restant. Pour trouver efficacement le plus long préfixe palindromique, utilisez la fonction d’échec de KMP sur la chaîne s + '#' + reverse(s). La dernière valeur de la fonction d’échec donne la longueur du plus long préfixe palindromique.
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'Vérification rapide
Vérifiez votre compréhension des concepts de Structures de données & algorithmes — préparation aux entretiens de programmation présentés dans cette leçon.
Bilan de la leçon
Dans cette leçon, vous avez appris que : la détection de palindromes avec deux pointeurs s’exécute en O(n) et utilise O(1) d’espace — lorsque l’espace est important, privilégiez toujours les vérifications fondées sur les index plutôt que l’allocation d’une copie inversée ; l’expansion autour du centre trouve la plus longue sous-chaîne palindromique en O(n²) en considérant chacune des 2n-1 positions comme un centre potentiel de palindrome ; et le codage par longueurs de séquences compresse les suites consécutives en O(n), tandis que le décodage nécessite une pile pour la variante à crochets imbriqués. Nous allons maintenant étudier le tri à bulles et le tri par insertion.
Questions Fréquemment Posées
La leçon « Codage, inversion et palindromes de chaînes » est-elle gratuite ?
Oui — le texte complet de « Codage, inversion et palindromes de chaînes » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Coding Interview Prep, passe à CoddyKit PRO. Le cours Coding Interview Prep comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Codage, inversion et palindromes de chaînes » ?
Implémentez l’inversion de mots en place, le codage par plages et la détection de palindromes, notamment la technique d’expansion autour du centre. Tu pratiques Coding Interview Prep avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer Coding Interview Prep ?
Aucune expérience préalable n'est requise. Coding Interview Prep sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 4 sur 4.
Combien de temps prend la leçon « Codage, inversion et palindromes de chaînes » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon Coding Interview Prep ?
Oui. Chaque leçon Coding Interview Prep inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- API des chaînes Python pour les entretiens
- Fenêtre glissante pour les sous-chaînes
- Anagrammes et tables de fréquences de caractères
- Codage, inversion et palindromes de chaînes