Given two strings word1 and word2, find the minimum number of operations required to convert word1 into word2. You can insert a character, delete a character, or replace a character.
For example, given word1 = "horse" and word2 = "ros", the minimum edit distance is 3: horse -> rorse (replace h with r) -> rose (delete r) -> ros (delete e).
Explain your approach to solving this problem and state the time and space complexity.
How to approach it
- Hint 1
Build a 2D table where each cell represents the edit distance between prefixes of the two strings.
- Hint 2
When characters match, no operation is needed and you take the diagonal value. When they differ, consider all three operations.
- Hint 3
dp[i][j] = edit distance between word1[0..i-1] and word2[0..j-1]. If characters match, dp[i][j] = dp[i-1][j-1]. Otherwise, dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]).
Ready to answer it out loud?
Record your answer in 1:30 and Preptile scores it 1–10 with specifics — what landed, what you skipped, and what to say next time.
Practising needs an invite code. Join the waitlist and we’ll send you one.