Edit distance measures the minimum insertions, deletions, and substitutions to transform one string into another. Vladimir Levenshtein defined this distance in 1965, and the Wagner-Fischer algorithm fills the table in O(mn) time and space, where m and n are the lengths of the two strings.
Each cell's value is the minimum of three options: the cell above plus 1 (deletion), the cell to the left plus 1 (insertion), or the diagonal cell plus 0 if the characters match (or plus 1 for a substitution). This recurrence guarantees that every cell captures the cheapest way to align the prefixes up to that point.
The traceback follows the path of minimum-cost decisions backward from the bottom-right corner to the top-left, revealing the optimal edit script. Each step in the path corresponds to a keep, insert, delete, or substitute operation.
Watch the table fill left to right, top to bottom. The highlighted arrows show which subproblems feed each cell. When complete, the traceback reveals the optimal sequence of operations. The bottom-right cell is the answer.
Wikipedia