Edit Distance
Given two strings word1 and word2, find the minimum number of operations to convert word1 into word2. Each operation inserts a character, deletes a character, or replaces a character, and each one counts as a single step regardless of which character it touches.
Input & Output
Input
word1 — the string to convert from
word2 — the string to convert to
Output
the minimum number of insert, delete, and replace operations that turn word1 into word2
Example
Input
word1 = "horse", word2 = "ros"
Output
3
Explanation
Replace h with r to get "rorse", delete the second r to get "rose", then delete e to get "ros". No two operations suffice.
Example
Input
word1 = "intention", word2 = "execution"
Output
5
Explanation
Both words end in "tion", so only the front has to change: "intention" → "inention" (delete t) → "enention" (replace i with e) → "exention" (replace n with x) → "exection" (replace n with c) → "execution" (insert u).
Constraints
0 <= word1.length, word2.length <= 500word1andword2consist of lowercase English letters