Edit Distance

Problem

Given two strings word1 and word2, return the minimum number of operations to convert word1 into word2, where each operation is one of: insert a character, delete a character, or replace a character. (LeetCode 72.)

Examples

One minimal path for the first: replace h with r (horse becomes rorse), delete r (rose), delete e (ros).

Constraints

0 ≤ word1.length, word2.length ≤ 500.

Attempt it first

This is the two-sequence 2D DP structural sibling of Longest Common Subsequence, but with THREE operations available instead of LCS's implicit two (match or skip). Before opening anything, define dp[i][j] = the minimum edits to convert the first i characters of word1 into the first j characters of word2, and work out what each of the three operations DOES to the indices i and j — that's the whole derivation.