Distância de Edição Passo a Passo
Insira, exclua e substitua para transformar.
Distância de Edição Passo a Passo é uma aula grátis de Competitive Programming Academy 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 Competitive Programming Academy, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Competitive Programming Academy inclui 4 aulas no total.
O que a distância de edição mede
Distância de edição é o menor número de edições de um único caractere necessário para transformar uma cadeia de caracteres em outra. Ela mede o quanto duas palavras realmente diferem.
As três operações
Você pode inserir, excluir ou substituir um caractere por edição. No problema padrão, cada operação custa exatamente um.
Defina o estado
Considere dp[i][j] como o número de edições necessárias para transformar os primeiros i caracteres de A nos primeiros j caracteres de B.
Coincidência gratuita
Se os caracteres atuais já coincidirem, nenhuma edição será necessária. Basta carregar o valor da diagonal diretamente para baixo.
if a[i-1] == b[j-1]:
dp[i][j] = dp[i-1][j-1]Caso contrário, pague um
Quando os caracteres forem diferentes, escolha o vizinho mais barato e some uma edição. Esse mínimo mais um abrange as três operações.
dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])Qual vizinho representa o quê
A célula acima representa uma exclusão, a célula à esquerda representa uma inserção e a diagonal representa uma substituição. O mínimo apenas escolhe a opção mais barata.
Casos base de cadeia vazia
Transformar uma cadeia de comprimento i em uma cadeia vazia exige i exclusões. Portanto, preencha a primeira linha e coluna com 0, 1, 2 e assim por diante.
for i in range(n+1):
dp[i][0] = i
for j in range(m+1):
dp[0][j] = jDimensione a tabela
Use uma grade de n+1 por m+1 para que os prefixos vazios tenham sua própria linha e coluna. Esse preenchimento mantém os laços simples.
dp = [[0] * (m+1) for _ in range(n+1)]Preencha na ordem
Percorra i e j começando em 1. Cada célula depende apenas dos vizinhos acima, à esquerda e na diagonal, que já foram preenchidos.
for i in range(1, n+1):
for j in range(1, m+1):
...Leia a distância
O menor número de edições acaba no canto. Sua resposta é dp[n][m] depois que a tabela estiver completa.
distance = dp[n][m]Custo e variações
Isso é executado em O(n vezes m) de tempo. Problemas reais podem atribuir custos diferentes a cada operação, mas a mesma recorrência continua funcionando.
Verificação rápida
Os caracteres A[i-1] e B[j-1] são diferentes. Qual recorrência fornece a distância de edição?
Recapitulação: distância de edição
Coincidência significa carregar a diagonal; diferença significa um mais o mínimo dos três vizinhos. Inicialize as bordas e leia dp[n][m]. ✏️
Perguntas Frequentes
A aula “Distância de Edição Passo a Passo” é grátis?
Sim — o texto completo de “Distância de Edição Passo a Passo” é 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 Competitive Programming Academy, atualize para CoddyKit PRO. O curso de Competitive Programming Academy inclui 4 aulas no total.
O que vou aprender em “Distância de Edição Passo a Passo”?
Insira, exclua e substitua para transformar. Você pratica Competitive Programming Academy 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 Competitive Programming Academy?
Nenhuma experiência prévia é necessária. Competitive Programming Academy 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 “Distância de Edição Passo a Passo”?
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 Competitive Programming Academy?
Sim. Cada aula de Competitive Programming Academy 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
- Contagem de Caminhos em uma Grade
- Soma Mínima de Caminho com Obstáculos
- Maior Subsequência Comum
- Distância de Edição Passo a Passo