Edit distance and longest common subsequence

Also written: edit distance, LCS, longest common subsequence

Two classic problems solved with a 2D dynamic programming table: edit distance counts the letter changes that turn one word into another, and the longest common subsequence finds the longest run of letters that appear in both words in the same order.