Mengekspresikan permutasi sewenang-wenang sebagai urutan operasi (masukkan, pindahkan, hapus)

Misalkan saya punya dua string. Panggil mereka dan B . Tidak ada string yang memiliki karakter berulang.$A$$B$

Bagaimana saya dapat menemukan urutan tersingkat dari memasukkan, memindahkan, dan menghapus operasi yang mengubah menjadi B , di mana:$A$$B$

• insert(char, offset)menyisipkan charpada yang diberikan offsetdalam string
• move(from_offset, to_offset)memindahkan karakter saat ini di offset from_offsetke posisi baru sehingga telah diimbangito_offset
• delete(offset) menghapus karakter di offset

Contoh aplikasi: Anda melakukan kueri basis data dan menunjukkan hasilnya di situs web Anda. Kemudian, Anda menjalankan kembali kueri basis data dan menemukan bahwa hasilnya telah berubah. Anda ingin mengubah apa yang ada di halaman agar sesuai dengan apa yang ada di database menggunakan jumlah minimum operasi DOM. Ada dua alasan mengapa Anda menginginkan urutan operasi terpendek. Pertama, efisiensi. Ketika hanya beberapa catatan yang berubah, Anda ingin memastikan bahwa Anda melakukan daripada O ( n $\mathcal{O}(1)$$\mathcal{O}(n)$Operasi DOM, karena mahal. Kedua, benar. Jika item dipindahkan dari satu posisi ke posisi lain, Anda ingin memindahkan node DOM terkait dalam satu operasi, tanpa menghancurkan dan membuatnya kembali. Kalau tidak, Anda akan kehilangan status fokus, konten <input>elemen, dan sebagainya.

Saya sarankan untuk melihat pada algoritma edit jarak . Alih-alih hanya menghitung jarak, Anda akan ingin mencatat jalur berat minimum Anda melalui array dan mengembalikannya.