Codificação, Reversão e Palíndromos de Strings
Implemente a reversão de palavras in-place, a codificação por comprimento de sequência e a detecção de palíndromos, incluindo a técnica de expansão ao redor do centro.
Codificação, Reversão e Palíndromos de Strings é uma aula grátis de Coding Interview Prep no CoddyKit. Esta é a aula 4 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de Coding Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Coding Interview Prep inclui 4 aulas no total.
Inversão de uma Cadeia de Caracteres no Próprio Lugar
As cadeias de caracteres do Python são imutáveis, portanto a inversão "no próprio lugar" significa convertê-las em uma lista de caracteres, fazer a troca usando dois ponteiros e juntar os elementos. A troca clássica com dois ponteiros: coloque left no índice 0 e right no último índice; troque os caracteres e mova os ponteiros para dentro até que se cruzem. Isso requer tempo O(n) e espaço O(n) para a lista de caracteres — uma quantidade irredutível, pois as cadeias de caracteres são imutáveis.
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'Inversão de Palavras em uma Frase
Inverta a ordem das palavras e remova os espaços extras. A solução simples em Python: use split (que lida com vários espaços), inverta a lista e use join. Para fazer a inversão no próprio lugar em um vetor de caracteres: inverta o vetor inteiro e depois inverta cada palavra individualmente. Essa abordagem de duas passagens requer tempo O(n) e espaço O(n), inevitável com cadeias de caracteres do Python, pois elas são imutáveis.
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]))Detecção Simples de Palíndromos
Uma cadeia de caracteres é um palíndromo se for igual à sua inversão. A verificação mais rápida em Python é: s == s[::-1]. Para palíndromos que ignoram maiúsculas e minúsculas e contêm apenas caracteres alfanuméricos — a variação mais comum em entrevistas — normalize primeiro a cadeia: filtre os caracteres não alfanuméricos e converta tudo para minúsculas; depois faça a comparação. Ambas as abordagens requerem 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?')) # TrueDetecção de Palíndromos com Dois Ponteiros
Para usar espaço extra O(1), verifique se a cadeia é um palíndromo com dois ponteiros em vez de usar fatiamento. Coloque left em 0 e right no final. Ignore os caracteres não alfanuméricos, compare os caracteres restantes sem diferenciar maiúsculas de minúsculas e retorne falso quando houver uma divergência. Essa abordagem é mais detalhada, mas evita criar completamente a cadeia limpa — algo importante quando a memória é limitada.
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')) # TrueExpansão ao Redor do Centro para Encontrar o Maior Palíndromo
A técnica de expansão ao redor do centro encontra a maior subcadeia palindrômica em tempo O(n²), usando espaço extra O(1). Para cada caractere — palíndromos de comprimento ímpar — e para cada intervalo entre caracteres — palíndromos de comprimento par — expanda para fora enquanto os caracteres coincidirem. Acompanhe o melhor par (início, fim) encontrado. Há 2n-1 centros, e cada expansão requer O(n) no pior caso.
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'Prévia do Algoritmo de manacher
O algoritmo de manacher encontra a maior subcadeia palindrômica em tempo O(n), usando a ideia de que um palíndromo dentro de um palíndromo maior pode ser inicializado a partir de uma posição espelhada. Raramente se pede sua implementação em entrevistas, mas vale a pena saber que ele existe. A maioria dos entrevistadores aceita a abordagem de expansão ao redor do centro, em O(n²), como "suficientemente ótima" — mencione manacher como a solução teórica em O(n) se pedirem uma extensão.
# 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ção por Comprimento de Sequência
A codificação por comprimento de sequência (RLE) comprime caracteres repetidos consecutivamente: 'aaabbc' torna-se 'a3b2c1'. Implementação: percorra a cadeia com um ponteiro rápido para encontrar o fim de cada sequência, escreva o caractere e a contagem em uma lista de saída e depois use join. A entrada pode ser menor que a saída codificada quando as sequências são curtas — sempre verifique se a versão codificada é menor antes de retorná-la.
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ção de Cadeias Codificadas por Comprimento de Sequência
A decodificação de RLE lê os caracteres e as sequências de dígitos que os seguem, expandindo cada sequência. Às vezes, os entrevistadores apresentam a variação do LeetCode em que a codificação usa k[encoded_string] para subcadeias repetidas: por exemplo, 3[ab] → ababab. Essa variação aninhada exige uma pilha para lidar com vários níveis de aninhamento.
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'Palíndromo Válido II: Uma Exclusão Permitida
Dada uma cadeia de caracteres, retorne verdadeiro se for possível transformá-la em um palíndromo excluindo no máximo um caractere. Use dois ponteiros; na primeira divergência, verifique se s[left+1:right+1] ou s[left:right] é um palíndromo — isto é, tente ignorar cada um dos caracteres divergentes. Se um dos lados for um palíndromo, retorne verdadeiro. Essa abordagem gulosa funciona porque ignorar o caractere divergente é a única ação útil.
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')) # FalseParticionamento de Palíndromos I
Particione uma cadeia em todas as subcadeias que sejam palíndromos. Use retrocesso: a cada etapa, tente todos os prefixos da parte restante da cadeia; se um prefixo for um palíndromo, aplique recursão ao restante. Pré-calcule uma tabela booleana bidimensional is_pal[i][j] usando DP por intervalos para tornar as verificações de palíndromos O(1), reduzindo o retrocesso geral de O(n² × 2^n) para O(n × 2^n) — algo aceitável, pois gerar todas as partições é exponencial por natureza.
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']]Palíndromo Mais Curto: Dispersão de Cadeias
Encontre o palíndromo mais curto que pode ser obtido adicionando caracteres ao início de uma cadeia. A ideia principal é encontrar o maior prefixo palindrômico de s e depois adicionar, no início, a inversão do sufixo restante. Para encontrar esse prefixo palindrômico com eficiência, use a função de falha do KMP na cadeia s + '#' + reverse(s). O último valor da função de falha fornece o comprimento do maior prefixo palindrômico.
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ção Rápida
Teste sua compreensão dos conceitos de Estruturas de Dados e Algoritmos — Preparação para Entrevistas de Programação apresentados nesta lição.
Resumo da Lição
Nesta lição, você aprendeu que: a detecção de palíndromos com dois ponteiros requer tempo O(n) e espaço O(1) — prefira sempre verificações baseadas em índices em vez de alocar uma cópia invertida quando o espaço for importante; a expansão ao redor do centro encontra a maior subcadeia palindrômica em O(n²), tratando cada uma das 2n-1 posições como um possível centro de palíndromo; e a codificação por comprimento de sequência comprime sequências consecutivas em O(n), enquanto a decodificação exige uma pilha para a variação com colchetes aninhados. A seguir, exploraremos a ordenação por bolha e a ordenação por inserção.
Perguntas Frequentes
A aula “Codificação, Reversão e Palíndromos de Strings” é grátis?
Sim — o texto completo de “Codificação, Reversão e Palíndromos de Strings” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de Coding Interview Prep, atualize para CoddyKit PRO. O curso de Coding Interview Prep inclui 4 aulas no total.
O que vou aprender em “Codificação, Reversão e Palíndromos de Strings”?
Implemente a reversão de palavras in-place, a codificação por comprimento de sequência e a detecção de palíndromos, incluindo a técnica de expansão ao redor do centro. Você pratica Coding Interview Prep com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar Coding Interview Prep?
Nenhuma experiência prévia é necessária. Coding Interview Prep no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 4 de 4.
Quanto tempo leva a aula “Codificação, Reversão e Palíndromos de Strings”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de Coding Interview Prep?
Sim. Cada aula de Coding Interview Prep inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- API de Strings do Python para Entrevistas
- Janela Deslizante para Substrings
- Anagramas e Mapas de Frequência de Caracteres
- Codificação, Reversão e Palíndromos de Strings