Sign in
Skip to solution
hardDSA

How do you compute the edit distance between two strings?

610 views
01

Understand the problem

Explain Levenshtein distance.

dpstrings
02

Attempt it yourself

Sketch your approach before reading the solution — that's what interviews test.

Nudge consolestandby

Stuck? Beam a request up — the console returns a conceptual nudge that guides your logic without spoiling the implementation.

03

Study the solution

DP table where dp[i][j] is the edit distance of prefixes. If characters match, carry dp[i-1][j-1]; else 1 + min of insert, delete, replace. O(m×n) time; space can be reduced to O(min(m,n)) with rolling rows.

Solution ready — 2 min read

Classified // press E to declassify

04

Read the code

Levenshtein DP table
Run Playground
def edit_distance(a, b):
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            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])   # replace
    return dp[m][n]


# --- demo ---
print(edit_distance('horse', 'ros'))            # 3
print(edit_distance('intention', 'execution'))  # 5
05

Join the discussion

Discussion (0)

Sign in to join the discussion.

No responses yet. Be the first to share what you think.

Transmission complete // awaiting log

KEEP THE
STREAK ALIVE.

Dossier 116 of 127 decoded in the Data Structures & Algorithms track. One more won't hurt.

Back to track