2-D Dynamic Programming Two strings
560. Edit Distance
Medium 147 DSA Sheet
You are given two words, word1 and word2. Return the fewest operations that turn word1 into word2.
Each operation changes one letter, in one of three ways:
- Insert a letter at any position.
- Delete a letter.
- Replace a letter with a different letter.
Either word can be empty. Turning a word into itself takes no operations.
Example 1
Input: word1 = "brand", word2 = "hands"
Output:
3Explanation: Delete the r to get "band", replace the b with h to get "hand", and insert an s at the end.
Example 2
Input: word1 = "", word2 = "sky"
Output:
3Explanation: An empty word becomes "sky" by inserting its three letters.
Example 3
Input: word1 = "winter", word2 = "writer"
Output:
2Explanation: Insert an r after the w to get "wrinter", then delete the n.
Check your understanding
Work out the answer for this input before you write any code.
word1 = "below", word2 = "elbow"
Constraints
0 ≤ word1.length, word2.length ≤ 1000word1andword2hold only lowercase English letters.
Clarifying questions
What you would ask an interviewer before writing any code.