Ausdrücken einer beliebigen Permutation als Folge von (Einfügen, Verschieben, Löschen) Operationen

Angenommen, ich habe zwei Zeichenfolgen. Nennen sie und . Keine der Zeichenfolgen enthält wiederholte Zeichen.$A$$B$

Wie finde ich die kürzeste Folge von Einfüge-, Verschiebungs- und Löschvorgängen, die in verwandeln , wobei:$A$$B$

• insert(char, offset)fügt charan der offsetin der Zeichenfolge angegebenen ein
• move(from_offset, to_offset)Verschiebt das aktuell versetzte Zeichen an from_offseteine neue Position, sodass es versetzt istto_offset
• delete(offset) löscht das Zeichen bei offset

Beispielanwendung: Sie führen eine Datenbankabfrage durch und zeigen die Ergebnisse auf Ihrer Website an. Später führen Sie die Datenbankabfrage erneut aus und stellen fest, dass sich die Ergebnisse geändert haben. Sie möchten ändern, was auf der Seite angezeigt wird, um mit der aktuellen Anzahl der DOM-Vorgänge übereinzustimmen. Es gibt zwei Gründe, warum Sie die kürzeste Abfolge von Vorgängen wünschen. Erstens Effizienz. Wenn sich nur wenige Datensätze ändern, möchten Sie sicherstellen, dass Sie anstelle von O ( n ) $\mathcal{O}(1)$$\mathcal{O}(n)$DOM-Operationen, da sie teuer sind. Zweitens die Richtigkeit. Wenn ein Element von einer Position an eine andere verschoben wurde, möchten Sie die zugehörigen DOM-Knoten in einem einzigen Vorgang verschieben, ohne sie zu zerstören und neu zu erstellen. Andernfalls verlieren Sie den Fokusstatus, den Inhalt von <input>Elementen usw.

Ich schlage vor, einen Blick auf den Algorithmus für die Bearbeitungsentfernung zu werfen . Anstatt nur die Entfernung zu berechnen, möchten Sie Ihren Mindestgewichtspfad durch das Array aufzeichnen und diesen zurückgeben.