A distância de edição (ou distância de Levenshtein) mede o número mínimo de operações necessárias para transformar uma string em outra. As operações permitidas são: inserção, remoção e substituição de um caractere. Este problema fundamental aparece em corretores ortográficos, sistemas de busca com tolerância a erros (fuzzy matching), bioinformática (alinhamento de DNA), processamento de linguagem natural e detecção de plágio.
Nesta página, implementamos a solução completa em Rust com programação dinâmica, incluindo visualização da matriz DP, reconstrução das operações e variantes do problema.
O Problema
Entrada: Duas strings s e t.
Objetivo: Encontrar o número mínimo de operações para transformar s em t, onde cada operação pode:
- Inserir um caractere em qualquer posição
- Remover um caractere de qualquer posição
- Substituir um caractere por outro
Exemplo:
s = "gato"
t = "rato"
Distância = 1 (substituir 'g' por 'r')
s = "domingo"
t = "sábado"
Distância = 5
Abordagem Ingênua (Força Bruta)
A recursão direta testa todas as possibilidades:
/// Distância de edição recursiva ingênua.
/// Complexidade: O(3^(m+n)) — extremamente lenta.
fn edit_bruta(s: &[u8], t: &[u8], i: usize, j: usize) -> usize {
// Se uma string acabou, restam inserções/remoções
if i == 0 {
return j; // Inserir j caracteres
}
if j == 0 {
return i; // Remover i caracteres
}
// Se os caracteres são iguais, avança sem custo
if s[i - 1] == t[j - 1] {
return edit_bruta(s, t, i - 1, j - 1);
}
// Tenta as três operações e escolhe a melhor
let inserir = edit_bruta(s, t, i, j - 1); // Inserir t[j] em s
let remover = edit_bruta(s, t, i - 1, j); // Remover s[i]
let substituir = edit_bruta(s, t, i - 1, j - 1); // Substituir s[i] por t[j]
1 + inserir.min(remover).min(substituir)
}
fn main() {
let s = b"gato";
let t = b"rato";
println!(
"Distância: {}",
edit_bruta(s, t, s.len(), t.len())
); // 1
}
Identificando Subestrutura Ótima
A recorrência para a distância de edição:
Se s[i] == t[j]:
dp[i][j] = dp[i-1][j-1] (sem custo — caracteres iguais)
Senão:
dp[i][j] = 1 + min(
dp[i][j-1], // Inserir
dp[i-1][j], // Remover
dp[i-1][j-1] // Substituir
)
Casos base:
dp[i][0] = i (remover todos os caracteres de s)
dp[0][j] = j (inserir todos os caracteres de t)
As duas condições de DP são satisfeitas:
- Subestrutura ótima: a solução ótima para prefixos
s[1..i]et[1..j]se constrói a partir de subproblemas menores. - Subproblemas sobrepostos: os mesmos pares
(i, j)aparecem em múltiplas ramificações da recursão.
Visualização da Tabela DP
Para s = "gato" e t = "rato":
"" r a t o
+----+----+----+----+----+
"" | 0 | 1 | 2 | 3 | 4 |
+----+----+----+----+----+
g | 1 | 1 | 2 | 3 | 4 |
+----+----+----+----+----+
a | 2 | 2 | 1 | 2 | 3 |
+----+----+----+----+----+
t | 3 | 3 | 2 | 1 | 2 |
+----+----+----+----+----+
o | 4 | 4 | 3 | 2 | 1 |
+----+----+----+----+----+
Preenchimento de dp[1][1] ("g" -> "r"):
g != r, então:
Inserir: dp[1][0] + 1 = 2
Remover: dp[0][1] + 1 = 2
Substituir: dp[0][0] + 1 = 1 <-- mínimo
dp[1][1] = 1
Resultado: dp[4][4] = 1 (substituir 'g' por 'r')
Para um exemplo maior, s = "domingo" e t = "sabado":
"" s a b a d o
+----+----+----+----+----+----+----+
"" | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+----+----+----+----+----+----+----+
d | 1 | 1 | 2 | 3 | 4 | 4 | 5 |
+----+----+----+----+----+----+----+
o | 2 | 2 | 2 | 3 | 4 | 5 | 4 |
+----+----+----+----+----+----+----+
m | 3 | 3 | 3 | 3 | 4 | 5 | 5 |
+----+----+----+----+----+----+----+
i | 4 | 4 | 4 | 4 | 4 | 5 | 6 |
+----+----+----+----+----+----+----+
n | 5 | 5 | 5 | 5 | 5 | 5 | 6 |
+----+----+----+----+----+----+----+
g | 6 | 6 | 6 | 6 | 6 | 6 | 6 |
+----+----+----+----+----+----+----+
o | 7 | 7 | 7 | 7 | 7 | 7 | 6 |
+----+----+----+----+----+----+----+
Resultado: dp[7][6] = 6 (mas nota: "sábado" sem acento = 5 ops)
Complexidade
| Abordagem | Tempo | Espaço | Observação |
|---|---|---|---|
| Força Bruta | O(3^(m+n)) | O(m+n) pilha | Impraticável |
| Top-Down (Memoização) | O(m * n) | O(m * n) | m, n = comprimentos |
| Bottom-Up (Tabulação) | O(m * n) | O(m * n) | Iterativo |
| Otimizado (2 linhas) | O(m * n) | O(min(m, n)) | Sem reconstrução |
Implementação: Top-Down (Memoização)
use std::collections::HashMap;
/// Distância de edição com memoização.
fn edit_memo(
s: &[u8],
t: &[u8],
i: usize,
j: usize,
cache: &mut HashMap<(usize, usize), usize>,
) -> usize {
if i == 0 { return j; }
if j == 0 { return i; }
if let Some(&valor) = cache.get(&(i, j)) {
return valor;
}
let resultado = if s[i - 1] == t[j - 1] {
// Caracteres iguais — sem custo
edit_memo(s, t, i - 1, j - 1, cache)
} else {
// Mínimo entre inserir, remover e substituir
let ins = edit_memo(s, t, i, j - 1, cache);
let rem = edit_memo(s, t, i - 1, j, cache);
let sub = edit_memo(s, t, i - 1, j - 1, cache);
1 + ins.min(rem).min(sub)
};
cache.insert((i, j), resultado);
resultado
}
fn main() {
let s = b"gato";
let t = b"rato";
let mut cache = HashMap::new();
let dist = edit_memo(s, t, s.len(), t.len(), &mut cache);
println!("Distância de edição: {}", dist); // 1
cache.clear();
let s2 = b"algoritmo";
let t2 = b"altruismo";
let dist2 = edit_memo(s2, t2, s2.len(), t2.len(), &mut cache);
println!("Distância \"algoritmo\" -> \"altruismo\": {}", dist2); // 3
}
Implementação: Bottom-Up (Tabulação)
/// Distância de edição com tabulação bottom-up.
/// Retorna a distância e a tabela DP para reconstrução.
fn edit_tabular(s: &str, t: &str) -> (usize, Vec<Vec<usize>>) {
let s_bytes = s.as_bytes();
let t_bytes = t.as_bytes();
let m = s_bytes.len();
let n = t_bytes.len();
// Tabela (m+1) x (n+1)
let mut dp = vec![vec![0usize; n + 1]; m + 1];
// Casos base: transformar string vazia
for i in 0..=m {
dp[i][0] = i; // Remover i caracteres de s
}
for j in 0..=n {
dp[0][j] = j; // Inserir j caracteres em s
}
// Preenchimento da tabela
for i in 1..=m {
for j in 1..=n {
if s_bytes[i - 1] == t_bytes[j - 1] {
dp[i][j] = dp[i - 1][j - 1]; // Sem custo
} else {
dp[i][j] = 1 + dp[i][j - 1] // Inserir
.min(dp[i - 1][j]) // Remover
.min(dp[i - 1][j - 1]); // Substituir
}
}
}
(dp[m][n], dp)
}
fn main() {
let (dist, _dp) = edit_tabular("gato", "rato");
println!("Distância: {}", dist); // 1
let (dist2, _dp2) = edit_tabular("algoritmo", "altruismo");
println!("Distância: {}", dist2); // 3
}
Otimização de Espaço
Cada linha depende apenas da anterior, então usamos duas linhas:
/// Distância de edição otimizada: O(m*n) tempo, O(min(m,n)) espaço.
fn edit_otimizado(s: &str, t: &str) -> usize {
let s_bytes = s.as_bytes();
let t_bytes = t.as_bytes();
// Usa a menor string como "coluna" para economia de espaço
let (curto, longo) = if s_bytes.len() <= t_bytes.len() {
(s_bytes, t_bytes)
} else {
(t_bytes, s_bytes)
};
let n = curto.len();
let mut anterior: Vec<usize> = (0..=n).collect();
let mut atual = vec![0usize; n + 1];
for i in 1..=longo.len() {
atual[0] = i;
for j in 1..=n {
if longo[i - 1] == curto[j - 1] {
atual[j] = anterior[j - 1];
} else {
atual[j] = 1 + atual[j - 1]
.min(anterior[j])
.min(anterior[j - 1]);
}
}
std::mem::swap(&mut anterior, &mut atual);
}
anterior[n]
}
fn main() {
println!("\"gato\" -> \"rato\": {}", edit_otimizado("gato", "rato"));
println!("\"rust\" -> \"trust\": {}", edit_otimizado("rust", "trust"));
println!("\"\" -> \"abc\": {}", edit_otimizado("", "abc"));
}
Reconstruindo a Solução
Para saber quais operações foram realizadas:
/// Tipos de operação de edição.
#[derive(Debug)]
enum Operacao {
Manter(char), // Caractere igual, sem custo
Substituir(char, char), // Trocar um caractere por outro
Inserir(char), // Inserir caractere de t
Remover(char), // Remover caractere de s
}
/// Reconstrói as operações a partir da tabela DP.
fn reconstruir_operacoes(dp: &[Vec<usize>], s: &str, t: &str) -> Vec<Operacao> {
let s_bytes = s.as_bytes();
let t_bytes = t.as_bytes();
let mut i = s_bytes.len();
let mut j = t_bytes.len();
let mut ops = Vec::new();
while i > 0 || j > 0 {
if i > 0 && j > 0 && s_bytes[i - 1] == t_bytes[j - 1] {
ops.push(Operacao::Manter(s_bytes[i - 1] as char));
i -= 1;
j -= 1;
} else if j > 0 && (i == 0 || dp[i][j - 1] <= dp[i - 1][j].min(
if i > 0 { dp[i - 1][j - 1] } else { usize::MAX }
)) {
ops.push(Operacao::Inserir(t_bytes[j - 1] as char));
j -= 1;
} else if i > 0 && (j == 0 || dp[i - 1][j] <= dp[i - 1].get(j.wrapping_sub(1)).copied().unwrap_or(usize::MAX)) {
ops.push(Operacao::Remover(s_bytes[i - 1] as char));
i -= 1;
} else {
ops.push(Operacao::Substituir(s_bytes[i - 1] as char, t_bytes[j - 1] as char));
i -= 1;
j -= 1;
}
}
ops.reverse();
ops
}
fn main() {
let s = "gato";
let t = "rato";
let (dist, dp) = edit_tabular(s, t);
let ops = reconstruir_operacoes(&dp, s, t);
println!("Distância: {}", dist);
println!("Operações:");
for op in &ops {
match op {
Operacao::Manter(c) => println!(" Manter '{}'", c),
Operacao::Substituir(de, para) => println!(" Substituir '{}' -> '{}'", de, para),
Operacao::Inserir(c) => println!(" Inserir '{}'", c),
Operacao::Remover(c) => println!(" Remover '{}'", c),
}
}
}
fn edit_tabular(s: &str, t: &str) -> (usize, Vec<Vec<usize>>) {
let s_bytes = s.as_bytes();
let t_bytes = t.as_bytes();
let m = s_bytes.len();
let n = t_bytes.len();
let mut dp = vec![vec![0usize; n + 1]; m + 1];
for i in 0..=m { dp[i][0] = i; }
for j in 0..=n { dp[0][j] = j; }
for i in 1..=m {
for j in 1..=n {
if s_bytes[i - 1] == t_bytes[j - 1] {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = 1 + dp[i][j - 1].min(dp[i - 1][j]).min(dp[i - 1][j - 1]);
}
}
}
(dp[m][n], dp)
}
Aplicação: Corretor Ortográfico Simples
/// Encontra as palavras mais próximas de um termo digitado incorretamente.
fn sugerir_correcoes(palavra: &str, dicionario: &[&str], max_dist: usize) -> Vec<(String, usize)> {
let mut sugestoes: Vec<(String, usize)> = dicionario
.iter()
.map(|&p| {
let dist = edit_otimizado(palavra, p);
(p.to_string(), dist)
})
.filter(|(_p, d)| *d <= max_dist)
.collect();
sugestoes.sort_by_key(|(_p, d)| *d);
sugestoes
}
fn edit_otimizado(s: &str, t: &str) -> usize {
let s = s.as_bytes();
let t = t.as_bytes();
let (curto, longo) = if s.len() <= t.len() { (s, t) } else { (t, s) };
let n = curto.len();
let mut ant: Vec<usize> = (0..=n).collect();
let mut cur = vec![0; n + 1];
for i in 1..=longo.len() {
cur[0] = i;
for j in 1..=n {
cur[j] = if longo[i - 1] == curto[j - 1] {
ant[j - 1]
} else {
1 + cur[j - 1].min(ant[j]).min(ant[j - 1])
};
}
std::mem::swap(&mut ant, &mut cur);
}
ant[n]
}
fn main() {
let dicionario = &["rust", "rústico", "justo", "robusto", "custo", "busto", "fuste"];
let palavra = "rustp";
let sugestoes = sugerir_correcoes(palavra, dicionario, 2);
println!("Sugestões para \"{}\":", palavra);
for (p, d) in &sugestoes {
println!(" {} (distância: {})", p, d);
}
}
Exercícios Práticos
Distância de Damerau-Levenshtein: Adicione uma quarta operação — transposição de dois caracteres adjacentes. Exemplo: “ab” -> “ba” custa 1 (não 2). Modifique a recorrência.
Pesos diferentes: Modifique a solução para que inserção custe 1, remoção custe 1, mas substituição custe 2. Em que cenários isso faz sentido?
Alinhamento de sequências: Dado o contexto de bioinformática, implemente o algoritmo de Needleman-Wunsch (alinhamento global) com matriz de pontuação personalizada.
Edição com custo mínimo total: Cada operação tem um custo que varia por caractere (por exemplo, trocar letras adjacentes no teclado custa menos). Implemente com uma função de custo parametrizável.
Veja Também
- String — Strings em Rust — manipulação de strings e codificação UTF-8
- Vec — Vetores dinâmicos — base para a matriz DP
- Slice — Fatias — acesso eficiente a bytes de strings
- Subsequência Comum Mais Longa (LCS) — problema relacionado com matriz DP similar
- Fibonacci com DP — introdução a programação dinâmica