Edit Distance
One of the classic problems solvable by dynamic programming
is computing the “edit distance” between two strings: the minimum number of
single-character insertions, deletions, or replacements required to convert one
string into another.
For example, the edit distance between “Hello” and “Jello”
is 1. The edit distance between “good” and “goodbye” is 3. The edit distance
between any string and itself is 0.
The edit distance can be used for such purposes as
suggesting, in a spell checker, a list of plausible replacements for a
misspelled word. For each word not found in the dictionary (and therefore
presumably misspelled), list all words in the dictionary that are a small edit
distance way from the misspelling.
