Edit Distance

    DSA · Advanced

    Definition

    Edit distance is the minimum insertions, deletions and replacements to turn one string into another.

    Used in spell checkers and DNA comparison.

    Diagram

    horse → rosdistance 3

    Flowchart

    dp[i][0] = i, dp[0][j] = jMatch → diagonalElse 1 + min(insert, delete, replace)

    Example: Levenshtein distance

    a, b = 'horse', 'ros'
dp = [[i + j if i * j == 0 else 0 for j in range(len(b) + 1)] for i in range(len(a) + 1)]
for i in range(1, len(a) + 1):
    for j in range(1, len(b) + 1):
        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])
print(dp[-1][-1])

    Output: 3

    Complexity

    O(m × n)

    Key points

    • Space can be reduced to O(n)
    • Similar to LCS

    Interview questions

    What does each dp cell mean?

    Edits to convert the first i chars of a into the first j chars of b.

    More DSA topics

    ArraysLinked ListStackQueue