Edit Distance
AlgorithmsMediumCompute minimum insert, delete, and replace edits needed to convert strings.
Alt+Shift+E
Configuration Panel
Edit Distance DP Grid (backtrack path highlighted)
DP table is empty.
Time Complexity
O(N * M)
Space Complexity
O(N * M) table size
Conceptual Overview
The Edit Distance (Levenshtein Distance) problem measures the minimum number of single-character editing operations (Insert, Delete, Replace) required to change one string into another.
Recurrence Relation
dp[i][j] = dp[i-1][j-1] if A[i-1] == B[j-1] else 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
State Transitions
Compares paths: diagonal represents matching or replacing; top represents deleting from A; left represents inserting into A.
Source: CP-Algorithms dynamic programming reference