Edit Distance

Minimum insertions, deletions, and substitutions to transform one string into another. Foundation of spell checkers, autocorrect, and DNA sequence alignment.

Time: O(m × n)

Space: O(m × n)

2D DP Table

Levenshtein Distance

Source string

Target string

Speed: 700ms

FastSlow

Step 1 / 0start

Strings

Source:

Target:

DP Table

Match

Substitute

Insert

Delete

Backtrack path

Click Play to begin.

Algorithm Details

Time:O(m × n)

Space:O(m × n)

Space-optimized:O(min(m,n))

Type:2D DP

Recurrence

Match: dp[i][j] = dp[i-1][j-1]
Substitute: dp[i-1][j-1] + 1
Insert: dp[i][j-1] + 1
Delete: dp[i-1][j] + 1
Answer: dp[m][n]

Knowledge Check

Question 1 of 3

When two characters match in the Edit Distance table, what is dp[i][j]?

DSAverse

Dynamic Programming

Loading Dynamic Programming...

DP Table Filling

subproblems

O(2^n)→O(n)