Expressando uma permutação arbitrária como uma sequência de operações (inserir, mover, excluir)

Suponha que eu tenha duas cordas. Chamá-los de e . Nenhuma das cadeias possui caracteres repetidos.$A$$B$

Como posso encontrar a menor seqüência de operações de inserção, movimentação e exclusão que transforma em B , onde:$A$$B$

• insert(char, offset)insere charno dado offsetna string
• move(from_offset, to_offset)move o personagem atualmente em deslocamento from_offsetpara uma nova posição para que ele tenha deslocamentoto_offset
• delete(offset) exclui o caractere em offset

Exemplo de aplicativo: você faz uma consulta ao banco de dados e mostra os resultados no seu site. Mais tarde, execute novamente a consulta do banco de dados e descubra que os resultados foram alterados. Você deseja alterar o que está na página para corresponder ao que está atualmente no banco de dados usando o número mínimo de operações DOM. Há duas razões pelas quais você deseja a menor sequência de operações. Primeiro, eficiência. Quando apenas alguns registros são alterados, você deseja certificar-se de executar operações vez de DOM, pois elas são caras. Segundo, correção. Se um item for movido de uma posição para outra, você deseja mover os nós DOM associados em uma única operação, sem destruí-los e recriá-los. Caso contrário, você perderá o estado de foco, o conteúdo de$\mathcal{O}(1)$$\mathcal{O}(n)$<input> elementos e assim por diante.

Sugiro dar uma olhada no algoritmo de distância de edição . Em vez de apenas calcular a distância, registre seu caminho de peso mínimo através da matriz e retorne-o.