Edit Distance

DSA · Dynamic Programming

Theory

Edit distance (Levenshtein distance) is the minimum number of single-character insertions, deletions and substitutions needed to turn one string into another. "kitten" becomes "sitting" in 3 edits. The DP table dp[i][j] holds the edit distance between the first i characters of word A and the first j characters of word B. If the current characters match, dp[i][j] = dp[i-1][j-1]; otherwise it is 1 plus the minimum of deleting (dp[i-1][j]), inserting (dp[i][j-1]) or replacing (dp[i-1][j-1]). The first row and column are base cases: converting to or from an empty string costs i or j edits. The algorithm runs in O(m * n) time and can use O(n) memory by keeping only two rows.

Why we use it

It powers spell checkers, fuzzy search, DNA sequence comparison, plagiarism detection and data cleaning (matching "Mumbai" with "Mumbay").

When to use it

Use it to measure how similar two strings are, or to suggest corrections. For very long strings or huge datasets, use approximate or indexed methods.

How it works

  1. dp[i][0] = i, dp[0][j] = j
  2. For each i, j
  3. Characters equal? Yes: dp[i][j] = dp[i-1][j-1]. No: 1 + min(delete, insert, replace).
  4. Return dp[m][n]

Syntax

dp[i][j] = dp[i-1][j-1]                         if a[i-1] == b[j-1]
         = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])  otherwise
Time O(m*n)

Example

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], dp[i][j - 1], dp[i - 1][j - 1])
    return dp[m][n]

for a, b in [("kitten", "sitting"), ("Mumbai", "Mumbay"), ("data", "data"), ("", "abc")]:
    print(f"{a!r} -> {b!r}: {edit_distance(a, b)}")

words = ["python", "pandas", "spark", "pyspark"]
typo = "pyhton"
print("Did you mean:", min(words, key=lambda w: edit_distance(typo, w)))

Key points

DSA topics

Introduction to DSA

Arrays and Searching

Sorting Algorithms

Linked Lists

Stacks and Queues

Hashing

Trees

Heaps

Graphs

Algorithm Techniques

Classic Algorithms

Dynamic Programming

T
Tech Town
Log InSign Up Free
Home SQL Python DSA Power BI Snowflake Databricks Spark Gen AI Practice Problems Contest Blog

Data Structures & Algorithms

The complete DSA roadmap: theory, why and when to use every structure and algorithm, Big O complexity, and Python code you can run right here in the browser.

{{ sectionCount }}
Sections
{{ topicCount }}
Topics
Free
Forever
Hands-on practice Practice DSA Online 251 problems across 13 patterns, with hidden tests and step-by-step optimal solutions. Start practising →
Section {{ sec.num }}

{{ sec.label }}

DSA  /  {{ current.sectionLabel }}  /  {{ current.name }}

{{ current.name }}

Theory

{{ current.def }}

Why we use it

{{ current.why }}

When to use it

{{ current.when }}

Flowchart — how {{ current.name }} works
{{ nd.text }}
{{ nd.text }}
◇ {{ nd.text }}
Yes → {{ nd.yes }}
No → {{ nd.no }}
Step-by-step visualisation
{{ cell.v }}
{{ cell.i }} {{ cell.tag }}
Step {{ vizStepLabel }}: {{ vizNote }}
■ comparing ■ swapping / moving ■ done / found ■ out of range
Complexity & Pseudocode
{{ current.syntax }}
Example Code
{{ current.example }}
▶ Try It Live — runs real Python 3 in your browser (first run loads the engine)
{{ liveOutput }}
{{ liveError }}
Key Points — click to check off as you learn
  • {{ pt.mark }} {{ pt.text }}

Share this topic