← Back

🔬 String Surgery Lab

Edit Distance • Insert, Delete, Replace operations

📝 Transformation

📊 Edit Distance DP Table

📐 Edit Distance Formula

if s1[i] == s2[j]:
  dp[i][j] = dp[i-1][j-1]

else:
  dp[i][j] = 1 + min(
    dp[i][j-1], // insert
    dp[i-1][j], // delete
    dp[i-1][j-1] // replace
  )
From Length
-
To Length
-
Min Operations
?

🔧 Operations

Run to see operations...

🎨 Legend

■ Insert (←)
■ Delete (↑)
■ Replace (↖)
■ Match (↖)