Edit Distance

Hard · rating 1800 · dp, strings

Read two lines, strings a and b. Print the minimum number of single-character insertions, deletions, or substitutions needed to turn a into b (Levenshtein distance).

Constraints: 0 ≤ |a|, |b| ≤ 1000

Editorial

Edit Distance (Levenshtein distance) is a well-known dynamic-programming interview problem: the fewest single-character insertions, deletions, or substitutions to turn one string into another.

Approach

Let dp[i][j] be the edit distance between the first i characters of a and first j of b. If the current characters match, no edit is needed. Otherwise it's 1 plus the cheapest of insert, delete, or substitute.

if a[i-1] == b[j-1]:
    dp[i][j] = dp[i-1][j-1]
else:
    dp[i][j] = 1 + min(dp[i-1][j],    # delete
                       dp[i][j-1],    # insert
                       dp[i-1][j-1])  # substitute

Complexity

Time: O(n × m). Space: O(n × m), reducible to O(min(n, m)) with a rolling row.

Open Edit Distance in Code Arena →