Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

In the article Levenshtein distance Wikipedia says about the proof of invariant that:

This proof fails to validate that the number placed in d[i,j] is in fact minimal; this is more difficult to show, and involves an argument by contradiction in which we assume d[i,j] is smaller than the minimum of the three, and use this to show one of the three is not minimal.

So how can I show that d[i,j] is actually minimal? (informal proof is ok)

share|cite|improve this question

There is an optimal edit sequence in which the edit operations occur in order from left to right. There are only three options for the last edit operation: insert the last character of the target string, delete the last character of the source string, or replace the last character. Everything before the last edit operation must be optimal.

See section 5.5 of these notes.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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