hardDSA

How do you compute the edit distance between two strings?

Q: How do you compute the edit distance between two strings?

**Intuition.** dp[i][j] is the edit distance between the first i chars of a and the first j of b . If the current characters match, no new work — carry the diagonal. Otherwise you pay 1 for the cheapest of the three edits: **insert**, **delete**, or **replace**. each cell = min of three neighbors (+1) or the diagonal if chars match ↖ rep<

610 views

Understand the problem

Explain Levenshtein distance.

dpstrings

Attempt it yourself

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

Stuck? AI Nudge Available

Get a conceptual hint to guide your logic without spoiling the final implementation.

Study the solution

The solution is waiting

Give it an honest attempt first — then compare your thinking with the full walkthrough.

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

Join the discussion

Discussion (0)

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

When would you use BFS over Dijkstra for shortest paths?

What is a greedy algorithm?