Distância de Edição (Levenshtein)
Derive a recorrência da distância de edição para operações de inserção, exclusão e substituição e preencha a tabela DP para pares de strings de comprimentos variados.
Distância de Edição (Levenshtein) é uma aula grátis de Coding Interview Prep no CoddyKit. Esta é a aula 3 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.
O problema da distância de edição
Distância de edição (distância de Levenshtein, LeetCode 72) pergunta: qual é o número mínimo de operações de inserir, excluir ou substituir necessárias para transformar uma cadeia em outra? Por exemplo, para transformar 'horse' em 'ros': substituir 'h'→'r' (horse→rorse), excluir 'r' (rorse→rose), excluir 'e' (rose→ros) — 3 operações. A distância de edição é fundamental para corretores ortográficos, alinhamento de DNA e correspondência aproximada.
# Allowed operations:
# Insert: 'abc' → 'abXc' (insert X)
# Delete: 'abc' → 'ac' (delete b)
# Replace: 'abc' → 'aXc' (replace b with X)
# horse → ros: 3 operations
# 1. horse → rorse (replace h with r)
# 2. rorse → rose (delete r at index 1)
# 3. rose → ros (delete e)
print('Edit distance horse→ros: 3')
print('Edit distance intention→execution: 5')Estado e recorrência da DP
Defina dp[i][j] = distância mínima de edição entre word1[:i] e word2[:j]. Se word1[i-1] == word2[j-1], nenhuma operação é necessária: dp[i][j] = dp[i-1][j-1]. Caso contrário, escolha o mínimo entre três operações: inserir dp[i][j-1] + 1, excluir dp[i-1][j] + 1, substituir dp[i-1][j-1] + 1. Casos-base: dp[i][0] = i (excluir toda a word1) e dp[0][j] = j (inserir toda a word2).
def edit_distance(word1, word2):
m, n = len(word1), len(word2)
dp = [[0]*(n+1) for _ in range(m+1)]
# Base cases
for i in range(m+1): dp[i][0] = i # delete all of word1
for j in range(n+1): dp[0][j] = j # insert all of word2
for i in range(1, m+1):
for j in range(1, n+1):
if word1[i-1] == word2[j-1]:
dp[i][j] = dp[i-1][j-1] # no cost
else:
dp[i][j] = 1 + min(
dp[i][j-1], # insert
dp[i-1][j], # delete
dp[i-1][j-1] # replace
)
return dp[m][n]
print(edit_distance('horse', 'ros')) # 3
print(edit_distance('intention', 'execution')) # 5Entendendo as três operações
As três operações correspondem diretamente a movimentos na tabela de DP: Substituir dp[i-1][j-1]+1 — correspondemos os dois caracteres, mas pagamos um custo. Excluir de word1 dp[i-1][j]+1 — remova um caractere de word1 (mova-se para cima na tabela). Inserir em word1 dp[i][j-1]+1 — insira um caractere para corresponder a word2 (mova-se para a esquerda). O mínimo entre os três fornece o percurso ótimo de edições.
# Visualise the DP table for 'cat' → 'cut'
# dp[i][j] = min edits for word1[:i] vs word2[:j]
word1, word2 = 'cat', 'cut'
m, n = len(word1), len(word2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(m+1): dp[i][0] = i
for j in range(n+1): dp[0][j] = j
for i in range(1, m+1):
for j in range(1, n+1):
if word1[i-1]==word2[j-1]: dp[i][j]=dp[i-1][j-1]
else: dp[i][j]=1+min(dp[i][j-1],dp[i-1][j],dp[i-1][j-1])
print(' ', ' '.join(' '+word2))
for i, row in enumerate(dp):
print((' ' if i==0 else word1[i-1]), row)Otimização de espaço para O(n)
A distância de edição precisa apenas da linha atual e da linha anterior. Use um vetor unidimensional de tamanho n+1 e acompanhe o valor diagonal (dp[i-1][j-1]) separadamente antes de atualizar cada célula. Processe da esquerda para a direita: temp = dp[j] (valor antigo = dp[i-1][j]); atualize dp[j] usando dp[j] (exclusão), dp[j-1] (inserção) e diagonal (substituição).
def edit_distance_1d(word1, word2):
m, n = len(word1), len(word2)
dp = list(range(n + 1)) # initial row: 0,1,2,...,n
for i in range(1, m + 1):
diag = dp[0] # dp[i-1][0]
dp[0] = i # dp[i][0] = i
for j in range(1, n + 1):
temp = dp[j] # dp[i-1][j] before overwrite
if word1[i-1] == word2[j-1]:
dp[j] = diag
else:
dp[j] = 1 + min(dp[j], # delete
dp[j-1], # insert
diag) # replace
diag = temp
return dp[n]
print(edit_distance_1d('horse', 'ros')) # 3
print(edit_distance_1d('intention', 'execution')) # 5Reconstrução das operações de edição
Para reconstruir a sequência real de edições, percorra a tabela de DP em sentido inverso a partir de (m, n). Em cada célula: se word1[i-1] == word2[j-1], mova-se diagonalmente (nenhuma operação). Caso contrário, descubra qual dos três vizinhos produziu o mínimo e registre a operação correspondente. Isso produz o registro de edições em ordem inversa; inverta-o para obter a resposta final.
def edit_ops(word1, word2):
m, n = len(word1), len(word2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(m+1): dp[i][0]=i
for j in range(n+1): dp[0][j]=j
for i in range(1,m+1):
for j in range(1,n+1):
if word1[i-1]==word2[j-1]: dp[i][j]=dp[i-1][j-1]
else: dp[i][j]=1+min(dp[i][j-1],dp[i-1][j],dp[i-1][j-1])
ops, i, j = [], m, n
while i>0 or j>0:
if i>0 and j>0 and word1[i-1]==word2[j-1]:
i-=1; j-=1
elif j>0 and (i==0 or dp[i][j-1]<=dp[i-1][j] and dp[i][j-1]<=dp[i-1][j-1]):
ops.append(f'Insert {word2[j-1]} at pos {i}'); j-=1
elif i>0 and (j==0 or dp[i-1][j]<=dp[i][j-1] and dp[i-1][j]<=dp[i-1][j-1]):
ops.append(f'Delete {word1[i-1]} at pos {i-1}'); i-=1
else:
ops.append(f'Replace {word1[i-1]} with {word2[j-1]}'); i-=1; j-=1
return list(reversed(ops))
for op in edit_ops('horse', 'ros'): print(op)Verificação de uma distância de edição
Um problema mais simples de entrevista: duas cadeias estão exatamente a uma edição de distância? Isso pode ser resolvido em O(n) sem DP. Percorra ambas as cadeias simultaneamente. Em caso de não correspondência, tente as três operações (ignore um caractere em s1, ignore um em s2, ignore ambos) e verifique se as partes restantes são idênticas. Se ocorrerem duas não correspondências, retorne False. Essa abordagem gulosa evita a DP completa O(mn) quando você só precisa saber se a distância ≤ 1.
def is_one_edit_distance(s, t):
m, n = len(s), len(t)
if abs(m - n) > 1: return False
if m > n: return is_one_edit_distance(t, s) # ensure m <= n
for i in range(m):
if s[i] != t[i]:
if m == n:
return s[i+1:] == t[i+1:] # replace
else:
return s[i:] == t[i+1:] # insert into s (delete from t)
return m + 1 == n # all matched, lengths differ by 1
print(is_one_edit_distance('ab', 'acb')) # True (insert c)
print(is_one_edit_distance('ab', 'ab')) # False (zero edits)
print(is_one_edit_distance('ab', 'abc')) # True (append c)
print(is_one_edit_distance('ab', 'xyz')) # FalseComparação entre distância de edição e LCS
A distância de edição (com as três operações) e a LCS oferecem visões complementares da similaridade entre cadeias. A distância de edição conta a diferença; a LCS conta a similaridade. Quando apenas inserções e exclusões são permitidas (sem substituição), distância de edição = m + n - 2×LCS. Quando substituições são permitidas, a DP é um pouco diferente: a diagonal contribui com dp[i-1][j-1] quando há correspondência (custo zero) ou com dp[i-1][j-1]+1 em uma substituição. Ambos os algoritmos são executados em tempo O(mn).
def lcs_len(s1, s2):
m, n = len(s1), len(s2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1,m+1):
for j in range(1,n+1):
if s1[i-1]==s2[j-1]: dp[i][j]=dp[i-1][j-1]+1
else: dp[i][j]=max(dp[i-1][j],dp[i][j-1])
return dp[m][n]
def edit_insert_delete_only(s1, s2):
return len(s1) + len(s2) - 2 * lcs_len(s1, s2)
print(edit_insert_delete_only('sea', 'eat')) # 2
print(edit_distance('sea', 'eat')) # 2 (same here: replace not needed)Correspondência aproximada de cadeias
A distância de edição viabiliza a correspondência aproximada em aplicações reais. Um corretor ortográfico sugere correções que estejam a uma ou duas edições de distância da palavra digitada. O desafio em grande escala é evitar O(mn × dict_size) comparações. As soluções incluem árvores BK (uma árvore métrica para distância de edição), indexação de n-gramas e algoritmos de correspondência aproximada de cadeias, como Bitap. Entender a DP subjacente ajuda você a raciocinar sobre a eficiência dessas ferramentas de nível mais alto.
def spell_suggest(typed, dictionary, max_dist=2):
'''Return words in dictionary within max_dist edits of typed.'''
suggestions = []
for word in dictionary:
if abs(len(typed) - len(word)) <= max_dist:
if edit_distance(typed, word) <= max_dist:
suggestions.append(word)
return suggestions
def edit_distance(w1, w2):
dp = list(range(len(w2)+1))
for i,c1 in enumerate(w1,1):
prev = i
for j,c2 in enumerate(w2,1):
temp = dp[j]
dp[j] = prev if c1==c2 else 1+min(dp[j],prev,dp[j-1])
prev = temp
return dp[len(w2)]
dictionary = ['horse', 'worse', 'house', 'morse', 'nurse']
print(spell_suggest('harse', dictionary)) # horse, worse, house, morseDistância de edição ponderada
Em algumas aplicações, operações diferentes têm custos diferentes. Por exemplo, transpor caracteres adjacentes (um erro de digitação comum) pode custar menos que uma substituição completa. A distância de Damerau-Levenshtein adiciona a transposição como uma quarta operação. A DP é estendida para também verificar dp[i-2][j-2]+1 quando word1[i-1]==word2[j-2] e word1[i-2]==word2[j-1]. Isso modela com mais precisão os erros de digitação no teclado.
def damerau_levenshtein(s, t):
m, n = len(s), len(t)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(m+1): dp[i][0]=i
for j in range(n+1): dp[0][j]=j
for i in range(1,m+1):
for j in range(1,n+1):
cost = 0 if s[i-1]==t[j-1] else 1
dp[i][j] = min(
dp[i-1][j]+1, # delete
dp[i][j-1]+1, # insert
dp[i-1][j-1]+cost # replace
)
# Transposition
if i>1 and j>1 and s[i-1]==t[j-2] and s[i-2]==t[j-1]:
dp[i][j] = min(dp[i][j], dp[i-2][j-2]+1)
return dp[m][n]
print(damerau_levenshtein('CA', 'ABC')) # 2
print(damerau_levenshtein('ab', 'ba')) # 1 (transposition)Alinhamento de sequências de DNA
A bioinformática usa variantes da distância de edição para o alinhamento de sequências de DNA. O algoritmo de Needleman-Wunsch é uma DP de alinhamento global intimamente relacionada à LCS e à distância de edição, na qual uma correspondência vale +1, uma não correspondência vale -1 e uma lacuna (inserção/exclusão) recebe uma penalidade. A variante Smith-Waterman realiza o alinhamento local (encontra a subcadeia com melhor correspondência). Ambos são algoritmos de DP O(mn) com a mesma estrutura de preenchimento da tabela.
def needleman_wunsch(seq1, seq2, match=1, mismatch=-1, gap=-1):
m, n = len(seq1), len(seq2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(m+1): dp[i][0] = i * gap
for j in range(n+1): dp[0][j] = j * gap
for i in range(1,m+1):
for j in range(1,n+1):
score = match if seq1[i-1]==seq2[j-1] else mismatch
dp[i][j] = max(
dp[i-1][j-1] + score, # align
dp[i-1][j] + gap, # gap in seq2
dp[i][j-1] + gap # gap in seq1
)
return dp[m][n]
print(needleman_wunsch('GATTACA', 'GCATGCU')) # alignment scoreAbordagem da distância de edição em entrevistas
Quando lhe perguntarem sobre distância de edição em uma entrevista: (1) Confirme as operações permitidas (inserção/exclusão/substituição). (2) Defina claramente o estado da DP. (3) Escreva explicitamente os três casos e a recorrência. (4) Declare os casos-base: dp[i][0]=i e dp[0][j]=j. (5) Mencione a otimização de espaço O(n). (6) Se houver tempo, percorra um exemplo pequeno, como 'cat'→'cut' (1 substituição), para validar. O tempo O(mn) e o espaço O(mn) → O(n) são os limites de complexidade padrão.
# Clean interview solution
def min_distance(word1, word2):
m, n = len(word1), len(word2)
# O(n) space with rolling row
dp = list(range(n + 1))
for i in range(1, m + 1):
diag = dp[0] # dp[i-1][0]
dp[0] = i
for j in range(1, n + 1):
temp = dp[j]
if word1[i-1] == word2[j-1]:
dp[j] = diag
else:
dp[j] = 1 + min(dp[j], dp[j-1], diag)
diag = temp
return dp[n]
# Time: O(mn), Space: O(n)
print(min_distance('horse', 'ros')) # 3
print(min_distance('intention', 'execution')) # 5
print(min_distance('', 'abc')) # 3
print(min_distance('abc', '')) # 3Verificação rápida
Teste sua compreensão dos conceitos de Estruturas de Dados & Algoritmos — Preparação para Entrevistas de Programação desta lição.
Resumo da lição
Nesta lição, você aprendeu: distância de edição dp[i][j] = min(dp[i][j-1]+1, dp[i-1][j]+1, dp[i-1][j-1]+cost) com cost=0 quando há correspondência e 1 caso contrário, os casos-base dp[i][0]=i e dp[0][j]=j representam a transformação de ou para uma cadeia vazia, e a otimização de espaço O(n) usa um vetor unidimensional deslizante com uma variável diagonal. A seguir, aplicaremos a mesma técnica do vetor deslizante para reduzir o espaço das tabelas de DP 2D de O(mn) para O(min(m,n)).
Perguntas Frequentes
A aula “Distância de Edição (Levenshtein)” é grátis?
Sim — o texto completo de “Distância de Edição (Levenshtein)” é 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 “Distância de Edição (Levenshtein)”?
Derive a recorrência da distância de edição para operações de inserção, exclusão e substituição e preencha a tabela DP para pares de strings de comprimentos variados. 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 3 de 4.
Quanto tempo leva a aula “Distância de Edição (Levenshtein)”?
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
- Caminhos Únicos e Soma Mínima de Caminho em Grades
- Maior Subsequência Comum
- Distância de Edição (Levenshtein)
- Otimização de Espaço para DP 2D