9
$\begingroup$

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) inserts char at the given offset in the string
  • move(from_offset, to_offset) moves the character currently at offset from_offset to a new position so that it has offset to_offset
  • delete(offset) deletes the character at offset

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.

$\endgroup$

1 Answer 1

10
$\begingroup$

I suggest taking a look at the edit distance algorithm. Instead of just calculating the distance, you'll want to record your minimum weight path through the array and return that.

$\endgroup$
2
  • 5
    $\begingroup$ In fact, since there are no repetitions, this is a slightly simpler problem called the Ulam distance problem. While you can use the edit distance algorithm, there are faster methods targeted to this distance as well: mit.edu/~andoni/papers/ulamSublinear.pdf $\endgroup$
    – Suresh
    Mar 21, 2012 at 4:48
  • 1
    $\begingroup$ Edit distance does not usually cover move operations, so you might have to be vary when interpreting the score. $\endgroup$
    – Raphael
    Mar 21, 2012 at 13:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.