Edit distance (nee Levenshtein distance) is solved with dynamic programming, and is used by spell-checkers.

I agree reformulating the problem can be confusing. It wouldn't be worth it, but for the incredible efficiency gains (not always needed).