Edit Distance 30 XP Hard

LeetCode Ctrl+Enter Run Ctrl+S Save

Find the minimum number of operations (insert, delete, replace) to convert word1 to word2. Classic 2D DP.

# dp[i][j] = min ops to convert word1[:i] to word2[:j]
# If chars match: dp[i][j] = dp[i-1][j-1]
# Else: 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
#       (delete,    insert,     replace)

Base cases: dp[i][0] = i (delete all), dp[0][j] = j (insert all).

💡 Pro tip: Understand this problem deeply — don't just memorize the code. Try explaining the approach out loud as if teaching a friend. If you can explain it simply, you truly understand it!

📋 Instructions

Find minimum edit distance between 'horse' and 'ros'.

Build (m+1)×(n+1) DP table. Base cases on first row/column. Fill using the recurrence.

🧪 Test Cases

Input

minDistance('horse', 'ros')

Expected

3

Test case 1

← Previous Next Exercise →

main.py

Hi! I'm Rex 👋

Output

Ready. Press ▶ Run or Ctrl+Enter.

›