Suppose I have two strings. Call them $A$ and $B$. Neither string has any repeated characters.
How can I find the shortest sequence of insert, move, and delete operation that turns $A$ into $B$, where:
insert(char, offset)
insertschar
at the givenoffset
in the stringmove(from_offset, to_offset)
moves the character currently at offsetfrom_offset
to a new position so that it has offsetto_offset
delete(offset)
deletes the character atoffset
Example application: You do a database query and show the results on your website. Later, you rerun the database query and discover that the results have changed. You want to change what is on the page to match what is currently in the database using the minimum number of DOM operations. There are two reasons why you'd want the shortest sequence of operations. First, efficiency. When only a few records change, you want to make sure that you do $\mathcal{O}(1)$ rather than $\mathcal{O}(n)$ DOM operations, since they are expensive. Second, correctness. If an item moved from one position to another, you want to move the associated DOM nodes in a single operation, without destroying and recreating them. Otherwise you will lose focus state, the content of <input>
elements, and so forth.