Coding interview problems › Dynamic Programming

🪙 Dynamic Programming Medium

Edit Distance (Levenshtein Distance)

Edit Distance (Levenshtein) explained: insert, delete and replace as three neighbours in a 2D DP table, O(m·n) tested Python, pitfalls and a live table visual.

Also searched as: edit distance dp · Levenshtein distance · minimum operations to convert one string to another

🧮

Try it live Free

2D DP Table: LCS & Edit Distance

Type two strings, choose Edit Distance, and watch the 2D table fill with arrows showing which neighbour won each cell, then trace the cheapest path back out of the grid.

Also useful: Recursion & the Call Stack

Open the playground →

The problem

Given two strings a and b, return the minimum number of single-character edits needed to turn a into b. An edit is inserting a character, deleting a character, or replacing one character with another.

Inputa = "horse", b = "ros"
Output3

horse -> rorse (replace h) -> rose (delete r) -> ros (delete e)

Inputa = "intention", b = "execution"
Output5

The key insight

Let dp[i][j] be the cost to turn the first i characters of a into the first j of b. If the last characters match, no edit is needed: dp[i-1][j-1]. Otherwise pay 1 plus the cheapest of three neighbours: replace (diagonal), delete from a (up), or insert into a (left).

Brute force first: Recursively trying all three edits at every mismatch is roughly O(3m+n).

Step-by-step approach

  1. Create a (m + 1) × (n + 1) table.
  2. Fill the borders: dp[i][0] = i (delete everything) and dp[0][j] = j (insert everything).
  3. For each cell, if a[i-1] == b[j-1] copy the diagonal dp[i-1][j-1].
  4. Otherwise dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]).
  5. Return dp[m][n].

Python solution

PYTHON 3tested
def min_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                 # delete all of a[:i]
    for j in range(n + 1):
        dp[0][j] = j                 # insert all of b[: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 - 1],  # replace
                                   dp[i - 1][j],      # delete
                                   dp[i][j - 1])      # insert
    return dp[m][n]

Complexity

TimeO(m · n)
SpaceO(m · n)

Each of the m × n cells takes O(1) work. Keeping only two rows reduces space to O(n).

Common mistakes

Frequently asked questions

What is the time and space complexity of Edit Distance?

O(m × n) time. The full table is O(m × n) space; a two-row version is O(min(m, n)) if you only need the distance.

Is edit distance the same as Levenshtein distance?

Yes. Levenshtein distance is the name for edit distance with insert, delete and replace each costing 1.

How is edit distance related to LCS?

If only insertions and deletions are allowed, the distance is m + n - 2 × LCS(a, b). Allowing replacements can make it smaller.

Where is edit distance used?

Spell checkers, fuzzy search, DNA alignment and comparing OCR output to ground truth all use edit distance or weighted versions of it.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Dynamic Programming Coin Change (DP) lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.