min operationsto convert
word1 [0, i-1]to
word2 [0, j-1]. (Techinique we used before: iterate from
- How to initialize
dp[j]? We can’t just initialize them all to
dp[i]means the min operations to convert
word1 [0, i-1]to an empty string. So, apparently,
dp[i] = i. Likewise,
dp[j] = j.
- For dp deduction, there are
word1[i-1] === word2[j-1], these 2 chars are the same, so
dp[i][j] = dp[i-1][j-1]
word1[i-1] !== word2[j-1], there are
3kinds of operations:
dp[i][j] = dp[i-1][j-1] + 1
- Add/Delete: Convert
word1 [0, i-2]to
word2 [0, i-1]or vice versa.
dp[i][j-1] + 1Or
dp[i-1][j] + 1. When to convert a longer one to a short one, it’s
deletion. In the reverse way, it’s
Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.
You have the following three operations permitted on a word:
- Insert a character
- Delete a character
- Replace a character
Input: word1 = "horse", word2 = "ros"