Edit Distance

Q: É possível resolver a distância de edição com um único array?

Sim. Preencha um único array row no próprio lugar, da esquerda para a direita. Antes de sobrescrever row[j] , ele ainda contém o valor da linha acima, e row[j-1] já contém o valor da linha atual. Apenas a diagonal é perdida, então salve o valor antigo de row[j] em uma variável e use-o como a diagonal para j + 1 .

DifícilProgramação dinâmica

+10

Você recebe duas palavras, word1 e word2. Uma edição altera word1 de uma entre três maneiras: inserir uma letra em qualquer posição, excluir uma letra ou substituir uma letra por outra diferente. Retorne o menor número de edições necessário para transformar word1 em word2.

Função

minDistance(word1: string, word2: string) → integer

word1string: a palavra que você edita
word2string: a palavra alcançar
Retornainteger: o menor número de inserções, exclusões e substituições que transformam word1 em word2

Restrições

1 ≤ word1.length ≤ 500
1 ≤ word2.length ≤ 500
Ambas as palavras contêm apenas letras minúsculas do alfabeto inglês.

Exemplos

Entrada: word1 = "spot"word2 = "stop"
Saída: 2
Explicação: Substitua o p por t e o t por p: spot se torna stot e, depois, stop. Uma edição não é suficiente, porque as palavras diferem em dois lugares e uma inserção ou exclusão mudaria o comprimento.

Entrada: word1 = "garden"word2 = "ardent"
Saída: 2
Explicação: Exclua o g para obter arden e, em seguida, insira t no final para obter ardent. Substituir letra por letra custaria 6, porque as duas palavras diferem em todas as posições.

Entrada: word1 = "rain"word2 = "shine"
Saída: 3
Explicação: Substitua r por s e a por h e, em seguida, insira e. Duas edições falham: r e a não estão em shine, então cada uma exige uma edição que mantenha o comprimento, e a palavra ainda precisa crescer em uma letra.

Para ir além

Você também pode retornar uma lista de edições mais curta, além da contagem?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

As edições interagem: garden e ardent diferem nas seis posições, mas duas edições são suficientes. Então, observe a última letra de cada palavra. Ou as duas coincidem, ou uma de três edições faz com que coincidam, e cada escolha deixa o mesmo problema em prefixos mais curtos. Uma tabela resolve cada par de prefixos uma única vez.

Experimente as três edições com recursão

Correta, mas não termina nos maiores testes

Intuição

Seja edits(i, j) o menor número de edições que transforma o sufixo word1[i:] em word2[j:]. Se as primeiras letras forem iguais, mantenha-as e avance os dois índices: gastar uma edição em uma letra correspondente nunca ajuda. Caso contrário, some 1 ao menor custo entre três chamadas: uma substituição avança os dois índices, a exclusão de word1[i] avança i, e a inserção de word2[j] avança j. Quando uma palavra acabar, cada letra que restar na outra custa uma edição.

Cada incompatibilidade inicia três chamadas: duas palavras de 15 letras sem nenhuma letra em comum levam a cerca de 6.7 × 10^10 chamadas. No entanto, há apenas (n+1) × (m+1) pares diferentes (i, j), então quase todas as chamadas repetem uma chamada anterior.

Algoritmo

Se i ultrapassar o fim de word1, retorne m - j; se j ultrapassar o fim de word2, retorne n - i.
Se word1[i] == word2[j], retorne edits(i+1, j+1).
Caso contrário, retorne 1 + min(edits(i+1, j+1), edits(i+1, j), edits(i, j+1)).
A resposta é edits(0, 0).

def minDistance(word1, word2):
    n, m = len(word1), len(word2)

    def edits(i, j):
        # Fewest edits to turn word1[i:] into word2[j:]
        if i == n:
            return m - j  # insert the rest of word2
        if j == m:
            return n - i  # delete the rest of word1
        if word1[i] == word2[j]:
            return edits(i + 1, j + 1)
        return 1 + min(edits(i + 1, j + 1),  # replace word1[i] with word2[j]
                       edits(i + 1, j),      # delete word1[i]
                       edits(i, j + 1))      # insert word2[j]

    return edits(0, 0)

Preencha uma tabela de prefixos

Intuição

Seja dp[i][j] o menor número de edições para transformar as primeiras i letras de word1 nas primeiras j letras de word2. Se word1[i-1] for igual a word2[j-1], copie a diagonal dp[i-1][j-1]. Caso contrário, some 1 ao vizinho de menor custo: a diagonal corresponde a uma substituição, a célula acima a uma exclusão de word1[i-1] e a célula à esquerda a uma inserção de word2[j-1]. A linha e a coluna base não são zeros: transformar i letras em nada exige i exclusões, então dp[i][0] = i, e, da mesma forma, dp[0][j] = j.

Para transformar spot em stop, a última linha é [4, 3, 2, 2, 2]. A célula final compara t com p; sua diagonal (spo em sto) é 1 e seus outros vizinhos são 2, então a resposta é 1 + 1 = 2. Duas palavras de 500 letras preenchem 2.5 × 10^5 células, cada uma em tempo constante.

Algoritmo

Crie dp com (n+1) × (m+1) células, dp[i][0] = i e dp[0][j] = j.
Para i de 1 a n e j de 1 a m: se word1[i-1] == word2[j-1], defina dp[i][j] = dp[i-1][j-1].
Caso contrário, defina dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]).
Retorne dp[n][m].

def minDistance(word1, word2):
    n, m = len(word1), len(word2)
    # dp[i][j]: fewest edits to turn the first i letters of word1 into the first j of word2
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        dp[i][0] = i  # delete all i letters
    for j in range(m + 1):
        dp[0][j] = j  # insert all j letters
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(dp[i - 1][j - 1],  # replace
                                   dp[i - 1][j],      # delete word1[i-1]
                                   dp[i][j - 1])      # insert word2[j-1]
    return dp[n][m]

Mantenha apenas duas linhas

Intuição

A linha i lê apenas a linha i-1 e suas próprias células à esquerda, então dois arrays são suficientes: prev para a linha concluída e cur para a linha que você está preenchendo. A diagonal é prev[j-1], acima fica prev[j] e à esquerda fica cur[j-1]. A coluna base agora fica na primeira entrada de cada linha, então defina cur[0] = i antes de preencher a linha i.

Transformar word2 em word1 exige o mesmo número de edições, já que inserções e exclusões trocam de lugar. Troque as palavras para que as linhas percorram a mais curta: min(n, m) + 1 números por linha, em vez de uma tabela com até 251,001 células, com o mesmo trabalho de O(n × m).

Algoritmo

Se word2 for maior que word1, troque-os.
Defina prev = [0, 1, ..., m].
Para cada i de 1 a n, defina cur[0] = i e preencha cur[1..m] usando a regra da tabela, lendo a diagonal e acima de prev e à esquerda de cur. Em seguida, troque prev e cur.
Retorne prev[m].

def minDistance(word1, word2):
    if len(word2) > len(word1):
        word1, word2 = word2, word1  # the rows run along the shorter word
    m = len(word2)
    # prev[j]: fewest edits to turn the previous prefix of word1 into word2[:j]
    prev = list(range(m + 1))
    for i in range(1, len(word1) + 1):
        cur = [i] + [0] * m  # i letters into an empty prefix: delete them all
        for j in range(1, m + 1):
            if word1[i - 1] == word2[j - 1]:
                cur[j] = prev[j - 1]
            else:
                cur[j] = 1 + min(prev[j - 1],  # replace
                                 prev[j],      # delete word1[i-1]
                                 cur[j - 1])   # insert word2[j-1]
        prev = cur
    return prev[m]

Armadilhas e casos extremos

Preencher a linha 0 e a coluna 0 com zeros, como na maior subsequência comum. Transformar abc em um prefixo vazio custa 3 exclusões, não 0.
Esquecer cur[0] = i na versão de duas linhas. A primeira entrada mantém um valor de duas linhas antes, e todas as células depois dela ficam erradas.
Contabilizar uma edição quando há correspondência. Com 1 + min(...) para letras iguais, transformar a em a custa 1.
Ler o vizinho à esquerda de prev em vez de cur. À esquerda está a inserção de word2[j-1] na linha atual.
Recursão com memoização em Python para palavras de 500 letras. As chamadas chegam a 1000 níveis de profundidade, ultrapassando o limite padrão de recursão.

Perguntas frequentes3

Qual é a complexidade de tempo da distância de edição?

A solução com tabela preenche uma célula para cada par de prefixos em tempo constante: tempo O(n × m) para comprimentos n e m. Ela usa O(n × m) de memória para a tabela completa, ou O(min(n, m)) com duas linhas. A recursão simples sem uma tabela é exponencial.

A distância de edição é a mesma que a distância de Levenshtein?

Esta versão é a distância de Levenshtein: inserir, excluir e substituir custam uma unidade cada. Distância de edição é o nome da família. Apenas inserções e exclusões resultam em n + m - 2 × LCS; apenas substituições em sequências de mesmo comprimento resultam na distância de Hamming; e adicionar a troca de duas letras vizinhas resulta na versão de Damerau.

É possível resolver a distância de edição com um único array?

Sim. Preencha um único array row no próprio lugar, da esquerda para a direita. Antes de sobrescrever row[j], ele ainda contém o valor da linha acima, e row[j-1] já contém o valor da linha atual. Apenas a diagonal é perdida, então salve o valor antigo de row[j] em uma variável e use-o como a diagonal para j + 1.

def minDistance(word1, word2):
    # Escreva o código aqui

Teste #1

Teste #2

Teste #3

Argumentos

word1 = "spot"
word2 = "stop"

Saída Esperada

Edit Distance

Função

Restrições

Exemplos

Dicas

Solução

Experimente as três edições com recursão

Preencha uma tabela de prefixos

Mantenha apenas duas linhas

Armadilhas e casos extremos

Perguntas frequentes3

Problemas parecidos