232. Edit Distance (Levenshtein Distance)

Hard · Dynamic Programming

Given two strings `word1` and `word2`, return the minimum number of operations (insert, delete, replace) required to convert `word1` to `word2`.

Examples

Example 1
Input: word1="horse", word2="ros"
Output: 3
Explanation: horse→rorse (replace h→r), rorse→rose (delete r), rose→ros (delete e)
Example 2
Input: word1="", word2="abc"
Output: 3
Explanation: 3 insertions

Constraints