Edit Distance

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

A solução com tabela é executada em tempo O(n × m) , em que n e m são os dois comprimentos, porque preenche uma célula por par de prefixos com trabalho constante. 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 tabela, é exponencial.

Q: Como obter a lista de edições, e não apenas a quantidade?

Mantenha a tabela completa e volte a partir de dp[n][m] . Se as letras coincidirem, avance na diagonal sem fazer nenhuma edição. Caso contrário, avance para a célula vizinha cujo valor seja um a menos: a diagonal corresponde a uma substituição, subir corresponde a uma exclusão, ir para a esquerda corresponde a uma inserção. Pare em dp[0][0] e leia as edições na ordem inversa. A versão com duas linhas não consegue fazer isso sozinha, porque descartou as linhas anteriores.

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

Sim. Preencha um 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. O único valor que você perde é o da diagonal, então mantenha-o em uma variável: salve o valor antigo de row[j] antes de escrever e use-o como diagonal para j + 1 .

DifícilProgramação dinâmica

+10

Você recebe duas palavras, word1 e word2. Uma edição altera word1 de uma destas 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: Troque 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 alteraria 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 para obter shin e, em seguida, insira e. Duas edições não são suficientes: r e a não aparecem em shine, então cada uma delas custa uma edição que não aumenta o comprimento da palavra, e a palavra ainda precisa crescer uma letra.

+21 testes ocultos ao enviar

Para ir além

Você também pode retornar uma lista mais curta das edições, e não apenas informar quantas são?

Dicas

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

0 de 3 abertas

Solução

As edições interagem, então você não pode corrigir as letras posição por posição: garden e ardent diferem em todas as seis posições, mas duas edições bastam quando o g é excluído e tudo se desloca para a esquerda. A ideia que resolve isso é olhar apenas para a última letra de cada palavra. Ou as duas letras já coincidem, ou uma de exatamente três edições faz com que coincidam, e cada escolha deixa o mesmo problema em prefixos mais curtos. Uma tabela de respostas (n+1) × (m+1) resolve cada par de prefixos uma única vez, e duas linhas dela são suficientes.

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:]. Observe as primeiras letras dos dois sufixos. Se forem iguais, mantenha-as e avance os dois índices: uma letra correspondente nunca precisa de edição, e qualquer plano que gaste uma edição nela pode ser transformado em outro que a mantém sem ficar mais longo.

Se forem diferentes, alguma edição precisa lidar com word1[i] ou produzir word2[j], e há exatamente três maneiras. Substitua word1[i] por word2[j], e avance os dois índices: edits(i+1, j+1). Exclua word1[i], e avance apenas i: edits(i+1, j). Insira word2[j] antes dela, e avance apenas j: edits(i, j+1). A resposta é 1 mais o menor custo entre as três opções. Quando word1 acabar, insira o restante de word2, o que custa m - j; quando word2 acabar, exclua o restante de word1, o que custa n - i.

O algoritmo é lento porque cada diferença inicia três chamadas. Para duas palavras de 15 letras sem nenhuma letra em comum, isso representa cerca de 6.7 × 10^10 chamadas, e os testes grandes têm 500 letras cada. No entanto, há apenas (n+1) × (m+1) pares diferentes (i, j), então quase todas as chamadas repetem alguma chamada anterior.

Algoritmo

Escreva edits(i, j) para os sufixos que começam em i e j.
Se i estiver além do fim de word1, retorne m - j; se j estiver além do 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)) para substituir, excluir e inserir.
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

Estado. Seja dp[i][j] o menor número de edições necessárias para transformar as primeiras i letras de word1 nas primeiras j letras de word2. O índice 0 representa um prefixo vazio.

Transições. Compare as últimas letras dos dois prefixos, word1[i-1] e word2[j-1]. Se forem iguais, mantenha-as: dp[i][j] = dp[i-1][j-1], a célula na diagonal acima e à esquerda. Caso contrário, pague uma edição e escolha o menor valor entre três vizinhos. A diagonal dp[i-1][j-1] significa substituir word1[i-1] por word2[j-1]. A célula acima, dp[i-1][j], significa excluir word1[i-1]. A célula à esquerda, dp[i][j-1], significa inserir word2[j-1] no final.

Linha e coluna base. Ao contrário de muitos problemas de tabela, elas não são zeros. Transformar i letras em um prefixo vazio requer i exclusões, então dp[i][0] = i. Construir j letras do nada requer j inserções, então dp[0][j] = j. Cada célula consulta a célula acima, a que está à sua esquerda e a diagonal, então preencher linha por linha, da esquerda para a direita, garante que elas já estejam prontas. A resposta é dp[n][m].

Aqui está a tabela para transformar spot em stop, com colunas para os prefixos "", s, st, sto, stop. A linha "" é [0, 1, 2, 3, 4], a linha s é [1, 0, 1, 2, 3], a linha sp é [2, 1, 1, 2, 2], a linha spo é [3, 2, 2, 1, 2] e a linha spot é [4, 3, 2, 2, 2]. Observe algumas células. s comparado com s corresponde, então copia o valor diagonal 0. sp comparado com st não corresponde: seus vizinhos são 0 na diagonal, 1 acima e 1 à esquerda, então o valor é 1 + 0 = 1, uma substituição. spo comparado com sto corresponde no o e copia aquele 1. A última célula, spot comparado com stop, compara t com p: seus vizinhos são 1, 2 e 2, então a resposta é 1 + 1 = 2.

A tabela tem (n+1) × (m+1) células, com trabalho constante em cada uma, cerca de 2.5 × 10^5 passos para duas palavras de 500 letras. Uma recursão com memoização preenche as mesmas células, mas pode recursar até n + m chamadas de profundidade, o que ultrapassa o limite padrão de 1000 do Python.

Algoritmo

Crie uma tabela dp de (n+1) × (m+1) células.
Defina dp[i][0] = i para todo i e dp[0][j] = j para todo 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. Depois que uma linha é concluída, as linhas acima dela nunca mais são lidas. Mantenha dois arrays: prev para a linha concluída e cur para a linha que está sendo preenchida, e troque-os após cada linha. As transições não mudam: a diagonal é prev[j-1], acima é prev[j] e à esquerda é cur[j-1].

A coluna base não desaparece. Agora ela fica na primeira entrada de cada linha, então defina cur[0] = i antes de preencher a linha i. A linha 0 começa como [0, 1, 2, ..., m], a linha base.

Transformar word2 em word1 exige o mesmo número de edições, porque cada inserção se torna uma exclusão e cada exclusão, uma inserção. Então você pode trocar as palavras e fazer as linhas percorrerem a mais curta. Cada linha então contém min(n, m) + 1 números, em vez de uma tabela com até 251,001 células, e o trabalho continua sendo O(n × m).

Algoritmo

Se word2 for maior que word1, troque-os.
Defina prev = [0, 1, ..., m], em que m é o menor comprimento.
Para cada i de 1 a n, defina cur[0] = i e, em seguida, preencha cur[1..m] com a mesma regra, lendo a diagonal e o valor acima de prev e o valor à esquerda de cur.
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

A recorrência é curta, então a maioria dos bugs está nos casos base ou em qual vizinho é lido.

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, então dp[i][0] deve ser i e dp[0][j] deve ser j.
Esquecer cur[0] = i na versão com duas linhas. A primeira entrada mantém um valor de duas linhas atrás, e todas as células depois dela ficam erradas.
Cobrar uma edição quando há correspondência. dp[i][j] = 1 + min(...) para letras iguais faz com que transformar a em a custe 1. Quando há correspondência, copie a diagonal.
Ler o vizinho à esquerda de prev em vez de cur. A esquerda está na linha atual: é a inserção de word2[j-1] depois que word1[:i] já foi transformado em word2[:j-1].
Comparar posição por posição. Contar os lugares em que as palavras diferem ignora inserções e exclusões: isso dá 6 para garden e ardent, enquanto a resposta é 2.
Usar memoização com recursão em palavras de 500 letras. A profundidade das chamadas chega a 1000, que é o limite padrão do Python.

Perguntas frequentes4

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

A solução com tabela é executada em tempo O(n × m), em que n e m são os dois comprimentos, porque preenche uma célula por par de prefixos com trabalho constante. 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 tabela, é exponencial.

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

Sim, 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. Outras variantes permitem menos ou mais edições: somente inserções e exclusões resultam em n + m - 2 × LCS; somente 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.

Como obter a lista de edições, e não apenas a quantidade?

Mantenha a tabela completa e volte a partir de dp[n][m]. Se as letras coincidirem, avance na diagonal sem fazer nenhuma edição. Caso contrário, avance para a célula vizinha cujo valor seja um a menos: a diagonal corresponde a uma substituição, subir corresponde a uma exclusão, ir para a esquerda corresponde a uma inserção. Pare em dp[0][0] e leia as edições na ordem inversa. A versão com duas linhas não consegue fazer isso sozinha, porque descartou as linhas anteriores.

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

Sim. Preencha um 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. O único valor que você perde é o da diagonal, então mantenha-o em uma variável: salve o valor antigo de row[j] antes de escrever e use-o como diagonal para j + 1.

Python

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

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

word1 = "spot"
word2 = "stop"

Esperado

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 frequentes4

Problemas parecidos