Dynamic Programming
LC #72Hard
Edit Distance
Dynamic Programming
AmazonGoogleMetaBloombergMicrosoftProblem
Find the minimum number of operations (insert, delete, replace) to convert word1 to word2.
dynamic-programmingstring
Constraints
- ›0 ≤ word1.length, word2.length ≤ 500
- ›Lowercase English letters only
- ›Operations: insert, delete, replace (each costs 1)
Example
Input
word1 = "horse", word2 = "ros"Output
3Why
horse→rorse (replace h→r), rorse→rose (delete r), rose→ros (delete e)