Common Patterns - Learning Module

Loading content...

0/276

Edit Distance Variations

Measuring the Distance Between Strings

How different are two strings? Not in a philosophical sense, but in a precise, computable way that captures the effort required to transform one into the other?

The answer is Edit Distance, also known as Levenshtein Distance—the minimum number of single-character edits (insertions, deletions, or substitutions) needed to change one string into another. This deceptively simple metric underlies:

Spell checkers that suggest corrections for misspelled words
DNA sequence alignment in bioinformatics
Plagiarism detection systems measuring document similarity
Fuzzy search that finds matches despite typos
Natural language processing applications like machine translation

Edit distance is LeetCode problem #72, a classic DP problem that every serious engineer should master. But beyond the basic problem lie many fascinating variations with different edit operations, costs, and constraints.

What You Will Learn

By the end of this page, you will implement the classic edit distance algorithm, understand its variations (weighted edits, different allowed operations), explore space optimizations and path reconstruction, and see how edit distance connects to other string algorithms like LCS.

The Classic Edit Distance Problem

Problem Statement (LeetCode 72):

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2. You have three operations:

Insert a character
Delete a character
Replace a character

Example:

word1 = "horse"
word2 = "ros"

Transformation:
horse → rorse (replace 'h' with 'r')
rorse → rose  (delete 'r')
rose  → ros   (delete 'e')

Edit distance = 3

Historical Note:

This problem is named after Vladimir Levenshtein, who defined the metric in 1965. It's sometimes called "Levenshtein distance" in his honor. The algorithm we'll study was developed independently by Wagner and Fischer in 1974.

DP State Definition:

Let dp[i][j] = minimum edit distance to convert word1[0..i-1] to word2[0..j-1].

Using 1-indexed DP for clean base cases:

dp[i][0] = i (delete all i characters from word1)
dp[0][j] = j (insert all j characters into empty string)

The Recurrence:

At position (i, j), we consider the last character of each prefix:

Case 1: word1[i-1] == word2[j-1]

Characters match! No operation needed for this position.

dp[i][j] = dp[i-1][j-1]

Case 2: word1[i-1] != word2[j-1]

Characters differ. We must perform one of three operations:

Replace word1[i-1] with word2[j-1]: Now both end with the same character.
- Cost: 1 + dp[i-1][j-1]
Delete word1[i-1]: Remove it and match word1[0..i-2] with word2[0..j-1].
- Cost: 1 + dp[i-1][j]
Insert word2[j-1] after word1[i-1]: Now word1 ends with word2[j-1].
- Cost: 1 + dp[i][j-1]

dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])

Understanding Insert vs Delete

What's confusing is that "insert into word1" is equivalent to "delete from word2" when thinking about the transformation. The key is to think of dp[i][j] as "what's the cost to align word1[0..i-1] with word2[0..j-1]?" Insert extends word1; delete shortens word1; replace changes a character.

Implementation: 2D and Space-Optimized

edit_distance.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
def min_distance(word1: str, word2: str) -> int:
    """
    Compute the minimum edit distance (Levenshtein distance).
    
    Time Complexity: O(n * m) where n = len(word1), m = len(word2)
    Space Complexity: O(n * m) for the DP table
    
    Args:
        word1: Source string
        word2: Target string
    
    Returns:
        Minimum number of operations to transform word1 into word2
    """
    n, m = len(word1), len(word2)
    
    # Create DP table
    # dp[i][j] = min edits to convert word1[0..i-1] to word2[0..j-1]
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    
    # Base cases: transforming to/from empty string
    for i in range(n + 1):
        dp[i][0] = i  # Delete all characters
    for j in range(m + 1):
        dp[0][j] = j  # Insert all characters
    
    # Fill DP table
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if word1[i - 1] == word2[j - 1]:
                # Characters match - no operation needed
                dp[i][j] = dp[i - 1][j - 1]
            else:
                # Take minimum of three operations
                dp[i][j] = 1 + min(
                    dp[i - 1][j - 1],  # Replace
                    dp[i - 1][j],      # Delete from word1
                    dp[i][j - 1]       # Insert into word1
                )
    
    return dp[n][m]
 
 
def min_distance_optimized(word1: str, word2: str) -> int:
    """
    Space-optimized version using two rows.
    
    Time Complexity: O(n * m)
    Space Complexity: O(min(n, m)) - we use the shorter string for columns
    """
    # Ensure word2 is the shorter one for space efficiency
    if len(word1) < len(word2):
        word1, word2 = word2, word1
    
    n, m = len(word1), len(word2)
    
    # Use two rows: previous and current
    prev = list(range(m + 1))  # dp[i-1][*]
    curr = [0] * (m + 1)       # dp[i][*]
    
    for i in range(1, n + 1):
        curr[0] = i  # Base case: delete all from word1[0..i-1]
        
        for j in range(1, m + 1):
            if word1[i - 1] == word2[j - 1]:
                curr[j] = prev[j - 1]
            else:
                curr[j] = 1 + min(
                    prev[j - 1],  # Replace
                    prev[j],      # Delete
                    curr[j - 1]   # Insert
                )
        
        # Swap rows
        prev, curr = curr, prev
    
    return prev[m]  # Note: after swap, result is in prev
 
 
def min_distance_single_row(word1: str, word2: str) -> int:
    """
    Further optimized using single row.
    
    We need to save dp[i-1][j-1] before it's overwritten.
    
    Time: O(n * m)
    Space: O(m)
    """
    n, m = len(word1), len(word2)
    
    dp = list(range(m + 1))
    
    for i in range(1, n + 1):
        prev_diag = dp[0]  # dp[i-1][0]
        dp[0] = i          # dp[i][0] = i (base case)
        
        for j in range(1, m + 1):
            temp = dp[j]   # Save dp[i-1][j] before overwriting
            
            if word1[i - 1] == word2[j - 1]:
                dp[j] = prev_diag
            else:
                dp[j] = 1 + min(
                    prev_diag,  # Replace (dp[i-1][j-1])
                    dp[j],      # Delete (dp[i-1][j])
                    dp[j - 1]   # Insert (dp[i][j-1])
                )
            
            prev_diag = temp
    
    return dp[m]
 
 
# Demonstration with trace
def min_distance_with_trace(word1: str, word2: str) -> tuple[int, list[list[int]]]:
    """Return both the distance and the full DP table."""
    n, m = len(word1), len(word2)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    
    for i in range(n + 1):
        dp[i][0] = i
    for j in range(m + 1):
        dp[0][j] = j
    
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])
    
    return dp[n][m], dp
 
 
if __name__ == "__main__":
    examples = [
        ("horse", "ros"),
        ("intention", "execution"),
        ("", "abc"),
        ("abc", "abc"),
        ("abc", "def"),
    ]
    
    for w1, w2 in examples:
        dist = min_distance(w1, w2)
        dist_opt = min_distance_optimized(w1, w2)
        print(f"edit_distance('{w1}', '{w2}') = {dist} (optimized: {dist_opt})")

DP Table Visualization for "horse" → "ros":

      ""   r   o   s
""     0   1   2   3
 h     1   1   2   3
 o     2   2   1   2
 r     3   2   2   2
 s     4   3   3   2
 e     5   4   4   3

Reading the table:

dp[5][3] = 3 is our answer
Each cell shows the minimum operations to align that prefix of "horse" with that prefix of "ros"

Path Reconstruction: Finding the Actual Edits

Knowing the distance is useful, but often we need the actual sequence of edits. We can reconstruct the path by backtracking through the DP table.

Backtracking Strategy:

Starting from dp[n][m], we trace back to dp[0][0] by asking: "Which previous cell led to this value?"

If word1[i-1] == word2[j-1], we came from dp[i-1][j-1] (no operation)
Otherwise, we came from the minimum of the three neighbors:
- dp[i-1][j-1] → Replace operation
- dp[i-1][j] → Delete operation
- dp[i][j-1] → Insert operation

edit_distance_path.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
from enum import Enum
from dataclasses import dataclass
 
 
class EditOp(Enum):
    """Types of edit operations."""
    MATCH = "match"      # Characters already match
    REPLACE = "replace"  # Replace character
    DELETE = "delete"    # Delete from word1
    INSERT = "insert"    # Insert into word1
 
 
@dataclass
class Edit:
    """Represents a single edit operation."""
    operation: EditOp
    word1_idx: int      # Index in word1 (or -1 for insert)
    word2_idx: int      # Index in word2 (or -1 for delete)
    char_from: str = "" # Original character
    char_to: str = ""   # New character
 
 
def min_distance_with_path(
    word1: str, 
    word2: str
) -> tuple[int, list[Edit]]:
    """
    Compute edit distance and return the sequence of operations.
    
    Returns:
        Tuple of (distance, list of Edit operations)
    """
    n, m = len(word1), len(word2)
    
    # Build DP table
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    
    for i in range(n + 1):
        dp[i][0] = i
    for j in range(m + 1):
        dp[0][j] = j
    
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])
    
    # Backtrack to find the operations
    operations = []
    i, j = n, m
    
    while i > 0 or j > 0:
        if i > 0 and j > 0 and word1[i - 1] == word2[j - 1]:
            # Characters match - no operation
            operations.append(Edit(
                operation=EditOp.MATCH,
                word1_idx=i - 1,
                word2_idx=j - 1,
                char_from=word1[i - 1],
                char_to=word2[j - 1]
            ))
            i -= 1
            j -= 1
        elif i > 0 and j > 0 and dp[i][j] == dp[i-1][j-1] + 1:
            # Replace
            operations.append(Edit(
                operation=EditOp.REPLACE,
                word1_idx=i - 1,
                word2_idx=j - 1,
                char_from=word1[i - 1],
                char_to=word2[j - 1]
            ))
            i -= 1
            j -= 1
        elif i > 0 and dp[i][j] == dp[i-1][j] + 1:
            # Delete from word1
            operations.append(Edit(
                operation=EditOp.DELETE,
                word1_idx=i - 1,
                word2_idx=-1,
                char_from=word1[i - 1]
            ))
            i -= 1
        elif j > 0 and dp[i][j] == dp[i][j-1] + 1:
            # Insert into word1
            operations.append(Edit(
                operation=EditOp.INSERT,
                word1_idx=-1,
                word2_idx=j - 1,
                char_to=word2[j - 1]
            ))
            j -= 1
    
    # Reverse to get operations in forward order
    operations.reverse()
    
    return dp[n][m], operations
 
 
def apply_edits(word1: str, operations: list[Edit]) -> str:
    """
    Apply edit operations to transform word1, showing each step.
    """
    result = list(word1)
    offset = 0  # Track insertions/deletions affecting indices
    
    print(f"Starting: '{word1}'")
    
    for op in operations:
        if op.operation == EditOp.MATCH:
            continue  # No change needed
        
        if op.operation == EditOp.REPLACE:
            idx = op.word1_idx + offset
            result[idx] = op.char_to
            print(f"  Replace '{op.char_from}' at {idx} with '{op.char_to}' -> "
                  f"'{''.join(result)}'")
        
        elif op.operation == EditOp.DELETE:
            idx = op.word1_idx + offset
            del result[idx]
            offset -= 1
            print(f"  Delete '{op.char_from}' at {idx} -> '{''.join(result)}'")
        
        elif op.operation == EditOp.INSERT:
            # Insert at position corresponding to word2_idx
            idx = op.word2_idx + offset
            result.insert(idx, op.char_to)
            offset += 1
            print(f"  Insert '{op.char_to}' at {idx} -> '{''.join(result)}'")
    
    return ''.join(result)
 
 
# Demo
if __name__ == "__main__":
    word1, word2 = "horse", "ros"
    distance, operations = min_distance_with_path(word1, word2)
    
    print(f"\nTransforming '{word1}' to '{word2}':")
    print(f"Distance: {distance}")
    print(f"\nOperations:")
    for op in operations:
        if op.operation != EditOp.MATCH:
            print(f"  {op.operation.value}: {op.char_from or ''} -> {op.char_to or ''}")
    
    print(f"\nStep by step:")
    result = apply_edits(word1, operations)
    print(f"\nFinal: '{result}' (expected: '{word2}')")

Multiple Optimal Paths

When multiple cells tie for the minimum, there are multiple optimal edit sequences. Our backtracking algorithm picks one deterministically (preferring replace, then delete, then insert), but other valid sequences may exist.

Edit Distance Variations

The classic Levenshtein distance is just one member of a family of string metrics. Understanding the variations deepens your understanding and prepares you for different problem constraints.

1. Weighted Edit Distance

Different operations have different costs. Common in NLP where insertions might be "cheaper" than substitutions.

cost(insert) = 1
cost(delete) = 1  
cost(replace) = 2  # Penalize substitutions more heavily

2. Damerau-Levenshtein Distance

Adds transposition as a fourth operation (swap two adjacent characters). This models common typing errors better.

"ab" → "ba"  (1 transposition, vs 2 operations in Levenshtein)

3. Longest Common Subsequence (LCS) Distance

Only insertions and deletions are allowed (no substitutions). The edit distance equals n + m - 2*LCS(s, t).

4. Hamming Distance

Only substitutions are allowed. Strings must have equal length. Counts positions where characters differ.

5. One Edit Distance (LeetCode 161)

Determine if two strings are exactly one edit apart. A simpler problem with O(n) solution.

edit_distance_variations.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
def weighted_edit_distance(
    word1: str, 
    word2: str,
    insert_cost: int = 1,
    delete_cost: int = 1,
    replace_cost: int = 1
) -> int:
    """
    Edit distance with customizable operation costs.
    
    This allows modeling different types of errors.
    For example, in spell checking, substituting 'e' for 'a'
    might be cheaper than substituting 'e' for 'z' (nearby on keyboard).
    """
    n, m = len(word1), len(word2)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    
    for i in range(n + 1):
        dp[i][0] = i * delete_cost
    for j in range(m + 1):
        dp[0][j] = j * insert_cost
    
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = min(
                    dp[i - 1][j - 1] + replace_cost,
                    dp[i - 1][j] + delete_cost,
                    dp[i][j - 1] + insert_cost
                )
    
    return dp[n][m]
 
 
def damerau_levenshtein_distance(word1: str, word2: str) -> int:
    """
    Damerau-Levenshtein: adds transposition of adjacent characters.
    
    Transposition: "ab" → "ba" in one operation
    
    This requires a 2D table where we also look at dp[i-2][j-2]
    when word1[i-1] == word2[j-2] and word1[i-2] == word2[j-1].
    """
    n, m = len(word1), len(word2)
    
    # Use defaultdict for cleaner boundary handling
    from collections import defaultdict
    dp = defaultdict(lambda: float('inf'))
    
    for i in range(-1, n + 1):
        dp[i, -1] = i + 1
    for j in range(-1, m + 1):
        dp[-1, j] = j + 1
    
    for i in range(n):
        for j in range(m):
            cost = 0 if word1[i] == word2[j] else 1
            
            dp[i, j] = min(
                dp[i - 1, j] + 1,           # Delete
                dp[i, j - 1] + 1,           # Insert
                dp[i - 1, j - 1] + cost,    # Replace/Match
            )
            
            # Transposition
            if i > 0 and j > 0:
                if word1[i] == word2[j - 1] and word1[i - 1] == word2[j]:
                    dp[i, j] = min(dp[i, j], dp[i - 2, j - 2] + 1)
    
    return dp[n - 1, m - 1]
 
 
def is_one_edit_distance(s: str, t: str) -> bool:
    """
    LeetCode 161: One Edit Distance
    
    Check if strings are exactly one edit apart.
    
    Time: O(n)
    Space: O(1)
    """
    n, m = len(s), len(t)
    
    # Ensure s is shorter or equal
    if n > m:
        return is_one_edit_distance(t, s)
    
    # Length difference > 1 means more than one edit
    if m - n > 1:
        return False
    
    for i in range(n):
        if s[i] != t[i]:
            if n == m:
                # Replace: rest must match
                return s[i + 1:] == t[i + 1:]
            else:
                # Insert into s (or delete from t): s[i:] must match t[i+1:]
                return s[i:] == t[i + 1:]
    
    # All characters match; need exactly one insert at end
    return m == n + 1
 
 
def hamming_distance(s: str, t: str) -> int:
    """
    Hamming distance: count positions where characters differ.
    
    Strings must have equal length.
    Only substitutions are counted.
    """
    if len(s) != len(t):
        raise ValueError("Strings must have equal length for Hamming distance")
    
    return sum(c1 != c2 for c1, c2 in zip(s, t))
 
 
def lcs_based_distance(word1: str, word2: str) -> int:
    """
    LCS-based distance: only insertions and deletions.
    
    Distance = |word1| + |word2| - 2 * LCS_length
    
    This is the minimum edits when substitution is not allowed.
    """
    n, m = len(word1), len(word2)
    
    # Compute LCS length
    dp = [0] * (m + 1)
    for i in range(1, n + 1):
        prev = 0
        for j in range(1, m + 1):
            temp = dp[j]
            if word1[i - 1] == word2[j - 1]:
                dp[j] = prev + 1
            else:
                dp[j] = max(dp[j], dp[j - 1])
            prev = temp
    
    lcs_length = dp[m]
    return n + m - 2 * lcs_length
 
 
# Test all variations
if __name__ == "__main__":
    word1, word2 = "horse", "ros"
    
    print(f"Comparing '{word1}' and '{word2}':")
    print(f"  Levenshtein:         {weighted_edit_distance(word1, word2)}")
    print(f"  Weighted (rep=2):    {weighted_edit_distance(word1, word2, replace_cost=2)}")
    print(f"  Damerau-Levenshtein: {damerau_levenshtein_distance(word1, word2)}")
    print(f"  LCS-based:           {lcs_based_distance(word1, word2)}")
    
    # Transposition example
    print(f"\nTransposition example 'ab' vs 'ba':")
    print(f"  Levenshtein:         {weighted_edit_distance('ab', 'ba')}")
    print(f"  Damerau-Levenshtein: {damerau_levenshtein_distance('ab', 'ba')}")
    
    # One edit distance
    print(f"\nOne Edit Distance tests:")
    print(f"  'ab', 'acb': {is_one_edit_distance('ab', 'acb')}")  # True (insert)
    print(f"  'ab', 'a':   {is_one_edit_distance('ab', 'a')}")    # True (delete)
    print(f"  'ab', 'ac':  {is_one_edit_distance('ab', 'ac')}")   # True (replace)
    print(f"  'ab', 'ab':  {is_one_edit_distance('ab', 'ab')}")   # False (same)

Edit Distance Variations Comparison
Variant	Operations	Use Case	Complexity
Levenshtein	Insert, Delete, Replace	General spelling, DNA	O(nm)
Damerau-Levenshtein	Transposition	Typo correction	O(nm)
LCS-based	Insert, Delete only	Diff tools, version control	O(nm)
Hamming	Replace only (equal length)	Error correction codes	O(n)
Weighted	Custom costs per op	Domain-specific NLP	O(nm)

Real-World Applications

Edit distance is one of the most practically applied algorithms in computer science.

Spell Checking and Correction:

When you type "teh" and your editor suggests "the", edit distance is at work. The spell checker:

Detects "teh" isn't in the dictionary
Computes edit distance from "teh" to all dictionary words
Suggests words with smallest distances

Optimizations (like BK-trees) make this feasible for large dictionaries.

DNA Sequence Alignment:

In bioinformatics, comparing DNA sequences is fundamentally an edit distance problem. Researchers need to:

Find how similar two gene sequences are
Identify mutations (insertions, deletions, substitutions)
Align sequences for comparison

Variants like Needleman-Wunsch (global alignment) and Smith-Waterman (local alignment) extend edit distance with gap penalties.

Plagiarism Detection:

Plagiarism detectors compare submitted text against known sources. Since plagiarized text is often slightly modified (word substitutions, reordering), edit-distance-based similarity captures these subtle changes.

Diff Tools (Git, Unix diff):

When you run git diff, the output shows the minimum changes between file versions. This is computed using a variant of edit distance optimized for line-by-line comparison (the Myers diff algorithm).

Fuzzy Search:

Database systems and search engines support fuzzy matching—finding records that approximately match a query. This often uses edit distance with a threshold (e.g., "find all names within edit distance 2 of 'Smith'").

Industry Applications

•Google Search: "Did you mean?" suggestions for misspelled queries
•Grammarly/Word: Real-time spelling and grammar correction
•BLAST (Bioinformatics): Sequence alignment for genomic research
•ElasticSearch: Fuzzy query matching in full-text search
•Git/Mercurial: Computing minimal diffs between commits
•OCR Systems: Correcting recognition errors in scanned text

Edit Distance Variations

Measuring the Distance Between Strings

How different are two strings? Not in a philosophical sense, but in a precise, computable way that captures the effort required to transform one into the other?

Spell checkers that suggest corrections for misspelled words
DNA sequence alignment in bioinformatics
Plagiarism detection systems measuring document similarity
Fuzzy search that finds matches despite typos
Natural language processing applications like machine translation

What You Will Learn

The Classic Edit Distance Problem

Problem Statement (LeetCode 72):

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2. You have three operations:

Insert a character
Delete a character
Replace a character

Example:

word1 = "horse"
word2 = "ros"

Transformation:
horse → rorse (replace 'h' with 'r')
rorse → rose  (delete 'r')
rose  → ros   (delete 'e')

Edit distance = 3

Historical Note:

DP State Definition:

Let dp[i][j] = minimum edit distance to convert word1[0..i-1] to word2[0..j-1].

Using 1-indexed DP for clean base cases:

dp[i][0] = i (delete all i characters from word1)
dp[0][j] = j (insert all j characters into empty string)

The Recurrence:

At position (i, j), we consider the last character of each prefix:

Case 1: word1[i-1] == word2[j-1]

Characters match! No operation needed for this position.

dp[i][j] = dp[i-1][j-1]

Case 2: word1[i-1] != word2[j-1]

Characters differ. We must perform one of three operations:

Replace word1[i-1] with word2[j-1]: Now both end with the same character.
- Cost: 1 + dp[i-1][j-1]
Delete word1[i-1]: Remove it and match word1[0..i-2] with word2[0..j-1].
- Cost: 1 + dp[i-1][j]
Insert word2[j-1] after word1[i-1]: Now word1 ends with word2[j-1].
- Cost: 1 + dp[i][j-1]

dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])

Understanding Insert vs Delete

Implementation: 2D and Space-Optimized

edit_distance.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
def min_distance(word1: str, word2: str) -> int:
    """
    Compute the minimum edit distance (Levenshtein distance).
    
    Time Complexity: O(n * m) where n = len(word1), m = len(word2)
    Space Complexity: O(n * m) for the DP table
    
    Args:
        word1: Source string
        word2: Target string
    
    Returns:
        Minimum number of operations to transform word1 into word2
    """
    n, m = len(word1), len(word2)
    
    # Create DP table
    # dp[i][j] = min edits to convert word1[0..i-1] to word2[0..j-1]
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    
    # Base cases: transforming to/from empty string
    for i in range(n + 1):
        dp[i][0] = i  # Delete all characters
    for j in range(m + 1):
        dp[0][j] = j  # Insert all characters
    
    # Fill DP table
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if word1[i - 1] == word2[j - 1]:
                # Characters match - no operation needed
                dp[i][j] = dp[i - 1][j - 1]
            else:
                # Take minimum of three operations
                dp[i][j] = 1 + min(
                    dp[i - 1][j - 1],  # Replace
                    dp[i - 1][j],      # Delete from word1
                    dp[i][j - 1]       # Insert into word1
                )
    
    return dp[n][m]
 
 
def min_distance_optimized(word1: str, word2: str) -> int:
    """
    Space-optimized version using two rows.
    
    Time Complexity: O(n * m)
    Space Complexity: O(min(n, m)) - we use the shorter string for columns
    """
    # Ensure word2 is the shorter one for space efficiency
    if len(word1) < len(word2):
        word1, word2 = word2, word1
    
    n, m = len(word1), len(word2)
    
    # Use two rows: previous and current
    prev = list(range(m + 1))  # dp[i-1][*]
    curr = [0] * (m + 1)       # dp[i][*]
    
    for i in range(1, n + 1):
        curr[0] = i  # Base case: delete all from word1[0..i-1]
        
        for j in range(1, m + 1):
            if word1[i - 1] == word2[j - 1]:
                curr[j] = prev[j - 1]
            else:
                curr[j] = 1 + min(
                    prev[j - 1],  # Replace
                    prev[j],      # Delete
                    curr[j - 1]   # Insert
                )
        
        # Swap rows
        prev, curr = curr, prev
    
    return prev[m]  # Note: after swap, result is in prev
 
 
def min_distance_single_row(word1: str, word2: str) -> int:
    """
    Further optimized using single row.
    
    We need to save dp[i-1][j-1] before it's overwritten.
    
    Time: O(n * m)
    Space: O(m)
    """
    n, m = len(word1), len(word2)
    
    dp = list(range(m + 1))
    
    for i in range(1, n + 1):
        prev_diag = dp[0]  # dp[i-1][0]
        dp[0] = i          # dp[i][0] = i (base case)
        
        for j in range(1, m + 1):
            temp = dp[j]   # Save dp[i-1][j] before overwriting
            
            if word1[i - 1] == word2[j - 1]:
                dp[j] = prev_diag
            else:
                dp[j] = 1 + min(
                    prev_diag,  # Replace (dp[i-1][j-1])
                    dp[j],      # Delete (dp[i-1][j])
                    dp[j - 1]   # Insert (dp[i][j-1])
                )
            
            prev_diag = temp
    
    return dp[m]
 
 
# Demonstration with trace
def min_distance_with_trace(word1: str, word2: str) -> tuple[int, list[list[int]]]:
    """Return both the distance and the full DP table."""
    n, m = len(word1), len(word2)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    
    for i in range(n + 1):
        dp[i][0] = i
    for j in range(m + 1):
        dp[0][j] = j
    
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])
    
    return dp[n][m], dp
 
 
if __name__ == "__main__":
    examples = [
        ("horse", "ros"),
        ("intention", "execution"),
        ("", "abc"),
        ("abc", "abc"),
        ("abc", "def"),
    ]
    
    for w1, w2 in examples:
        dist = min_distance(w1, w2)
        dist_opt = min_distance_optimized(w1, w2)
        print(f"edit_distance('{w1}', '{w2}') = {dist} (optimized: {dist_opt})")

DP Table Visualization for "horse" → "ros":

      ""   r   o   s
""     0   1   2   3
 h     1   1   2   3
 o     2   2   1   2
 r     3   2   2   2
 s     4   3   3   2
 e     5   4   4   3

Reading the table:

dp[5][3] = 3 is our answer
Each cell shows the minimum operations to align that prefix of "horse" with that prefix of "ros"

Path Reconstruction: Finding the Actual Edits

Knowing the distance is useful, but often we need the actual sequence of edits. We can reconstruct the path by backtracking through the DP table.

Backtracking Strategy:

Starting from dp[n][m], we trace back to dp[0][0] by asking: "Which previous cell led to this value?"

If word1[i-1] == word2[j-1], we came from dp[i-1][j-1] (no operation)
Otherwise, we came from the minimum of the three neighbors:
- dp[i-1][j-1] → Replace operation
- dp[i-1][j] → Delete operation
- dp[i][j-1] → Insert operation

edit_distance_path.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
from enum import Enum
from dataclasses import dataclass
 
 
class EditOp(Enum):
    """Types of edit operations."""
    MATCH = "match"      # Characters already match
    REPLACE = "replace"  # Replace character
    DELETE = "delete"    # Delete from word1
    INSERT = "insert"    # Insert into word1
 
 
@dataclass
class Edit:
    """Represents a single edit operation."""
    operation: EditOp
    word1_idx: int      # Index in word1 (or -1 for insert)
    word2_idx: int      # Index in word2 (or -1 for delete)
    char_from: str = "" # Original character
    char_to: str = ""   # New character
 
 
def min_distance_with_path(
    word1: str, 
    word2: str
) -> tuple[int, list[Edit]]:
    """
    Compute edit distance and return the sequence of operations.
    
    Returns:
        Tuple of (distance, list of Edit operations)
    """
    n, m = len(word1), len(word2)
    
    # Build DP table
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    
    for i in range(n + 1):
        dp[i][0] = i
    for j in range(m + 1):
        dp[0][j] = j
    
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])
    
    # Backtrack to find the operations
    operations = []
    i, j = n, m
    
    while i > 0 or j > 0:
        if i > 0 and j > 0 and word1[i - 1] == word2[j - 1]:
            # Characters match - no operation
            operations.append(Edit(
                operation=EditOp.MATCH,
                word1_idx=i - 1,
                word2_idx=j - 1,
                char_from=word1[i - 1],
                char_to=word2[j - 1]
            ))
            i -= 1
            j -= 1
        elif i > 0 and j > 0 and dp[i][j] == dp[i-1][j-1] + 1:
            # Replace
            operations.append(Edit(
                operation=EditOp.REPLACE,
                word1_idx=i - 1,
                word2_idx=j - 1,
                char_from=word1[i - 1],
                char_to=word2[j - 1]
            ))
            i -= 1
            j -= 1
        elif i > 0 and dp[i][j] == dp[i-1][j] + 1:
            # Delete from word1
            operations.append(Edit(
                operation=EditOp.DELETE,
                word1_idx=i - 1,
                word2_idx=-1,
                char_from=word1[i - 1]
            ))
            i -= 1
        elif j > 0 and dp[i][j] == dp[i][j-1] + 1:
            # Insert into word1
            operations.append(Edit(
                operation=EditOp.INSERT,
                word1_idx=-1,
                word2_idx=j - 1,
                char_to=word2[j - 1]
            ))
            j -= 1
    
    # Reverse to get operations in forward order
    operations.reverse()
    
    return dp[n][m], operations
 
 
def apply_edits(word1: str, operations: list[Edit]) -> str:
    """
    Apply edit operations to transform word1, showing each step.
    """
    result = list(word1)
    offset = 0  # Track insertions/deletions affecting indices
    
    print(f"Starting: '{word1}'")
    
    for op in operations:
        if op.operation == EditOp.MATCH:
            continue  # No change needed
        
        if op.operation == EditOp.REPLACE:
            idx = op.word1_idx + offset
            result[idx] = op.char_to
            print(f"  Replace '{op.char_from}' at {idx} with '{op.char_to}' -> "
                  f"'{''.join(result)}'")
        
        elif op.operation == EditOp.DELETE:
            idx = op.word1_idx + offset
            del result[idx]
            offset -= 1
            print(f"  Delete '{op.char_from}' at {idx} -> '{''.join(result)}'")
        
        elif op.operation == EditOp.INSERT:
            # Insert at position corresponding to word2_idx
            idx = op.word2_idx + offset
            result.insert(idx, op.char_to)
            offset += 1
            print(f"  Insert '{op.char_to}' at {idx} -> '{''.join(result)}'")
    
    return ''.join(result)
 
 
# Demo
if __name__ == "__main__":
    word1, word2 = "horse", "ros"
    distance, operations = min_distance_with_path(word1, word2)
    
    print(f"\nTransforming '{word1}' to '{word2}':")
    print(f"Distance: {distance}")
    print(f"\nOperations:")
    for op in operations:
        if op.operation != EditOp.MATCH:
            print(f"  {op.operation.value}: {op.char_from or ''} -> {op.char_to or ''}")
    
    print(f"\nStep by step:")
    result = apply_edits(word1, operations)
    print(f"\nFinal: '{result}' (expected: '{word2}')")

Multiple Optimal Paths

Edit Distance Variations

The classic Levenshtein distance is just one member of a family of string metrics. Understanding the variations deepens your understanding and prepares you for different problem constraints.

1. Weighted Edit Distance

Different operations have different costs. Common in NLP where insertions might be "cheaper" than substitutions.

cost(insert) = 1
cost(delete) = 1  
cost(replace) = 2  # Penalize substitutions more heavily

2. Damerau-Levenshtein Distance

Adds transposition as a fourth operation (swap two adjacent characters). This models common typing errors better.

"ab" → "ba"  (1 transposition, vs 2 operations in Levenshtein)

3. Longest Common Subsequence (LCS) Distance

Only insertions and deletions are allowed (no substitutions). The edit distance equals n + m - 2*LCS(s, t).

4. Hamming Distance

Only substitutions are allowed. Strings must have equal length. Counts positions where characters differ.

5. One Edit Distance (LeetCode 161)

Determine if two strings are exactly one edit apart. A simpler problem with O(n) solution.

edit_distance_variations.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
def weighted_edit_distance(
    word1: str, 
    word2: str,
    insert_cost: int = 1,
    delete_cost: int = 1,
    replace_cost: int = 1
) -> int:
    """
    Edit distance with customizable operation costs.
    
    This allows modeling different types of errors.
    For example, in spell checking, substituting 'e' for 'a'
    might be cheaper than substituting 'e' for 'z' (nearby on keyboard).
    """
    n, m = len(word1), len(word2)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    
    for i in range(n + 1):
        dp[i][0] = i * delete_cost
    for j in range(m + 1):
        dp[0][j] = j * insert_cost
    
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = min(
                    dp[i - 1][j - 1] + replace_cost,
                    dp[i - 1][j] + delete_cost,
                    dp[i][j - 1] + insert_cost
                )
    
    return dp[n][m]
 
 
def damerau_levenshtein_distance(word1: str, word2: str) -> int:
    """
    Damerau-Levenshtein: adds transposition of adjacent characters.
    
    Transposition: "ab" → "ba" in one operation
    
    This requires a 2D table where we also look at dp[i-2][j-2]
    when word1[i-1] == word2[j-2] and word1[i-2] == word2[j-1].
    """
    n, m = len(word1), len(word2)
    
    # Use defaultdict for cleaner boundary handling
    from collections import defaultdict
    dp = defaultdict(lambda: float('inf'))
    
    for i in range(-1, n + 1):
        dp[i, -1] = i + 1
    for j in range(-1, m + 1):
        dp[-1, j] = j + 1
    
    for i in range(n):
        for j in range(m):
            cost = 0 if word1[i] == word2[j] else 1
            
            dp[i, j] = min(
                dp[i - 1, j] + 1,           # Delete
                dp[i, j - 1] + 1,           # Insert
                dp[i - 1, j - 1] + cost,    # Replace/Match
            )
            
            # Transposition
            if i > 0 and j > 0:
                if word1[i] == word2[j - 1] and word1[i - 1] == word2[j]:
                    dp[i, j] = min(dp[i, j], dp[i - 2, j - 2] + 1)
    
    return dp[n - 1, m - 1]
 
 
def is_one_edit_distance(s: str, t: str) -> bool:
    """
    LeetCode 161: One Edit Distance
    
    Check if strings are exactly one edit apart.
    
    Time: O(n)
    Space: O(1)
    """
    n, m = len(s), len(t)
    
    # Ensure s is shorter or equal
    if n > m:
        return is_one_edit_distance(t, s)
    
    # Length difference > 1 means more than one edit
    if m - n > 1:
        return False
    
    for i in range(n):
        if s[i] != t[i]:
            if n == m:
                # Replace: rest must match
                return s[i + 1:] == t[i + 1:]
            else:
                # Insert into s (or delete from t): s[i:] must match t[i+1:]
                return s[i:] == t[i + 1:]
    
    # All characters match; need exactly one insert at end
    return m == n + 1
 
 
def hamming_distance(s: str, t: str) -> int:
    """
    Hamming distance: count positions where characters differ.
    
    Strings must have equal length.
    Only substitutions are counted.
    """
    if len(s) != len(t):
        raise ValueError("Strings must have equal length for Hamming distance")
    
    return sum(c1 != c2 for c1, c2 in zip(s, t))
 
 
def lcs_based_distance(word1: str, word2: str) -> int:
    """
    LCS-based distance: only insertions and deletions.
    
    Distance = |word1| + |word2| - 2 * LCS_length
    
    This is the minimum edits when substitution is not allowed.
    """
    n, m = len(word1), len(word2)
    
    # Compute LCS length
    dp = [0] * (m + 1)
    for i in range(1, n + 1):
        prev = 0
        for j in range(1, m + 1):
            temp = dp[j]
            if word1[i - 1] == word2[j - 1]:
                dp[j] = prev + 1
            else:
                dp[j] = max(dp[j], dp[j - 1])
            prev = temp
    
    lcs_length = dp[m]
    return n + m - 2 * lcs_length
 
 
# Test all variations
if __name__ == "__main__":
    word1, word2 = "horse", "ros"
    
    print(f"Comparing '{word1}' and '{word2}':")
    print(f"  Levenshtein:         {weighted_edit_distance(word1, word2)}")
    print(f"  Weighted (rep=2):    {weighted_edit_distance(word1, word2, replace_cost=2)}")
    print(f"  Damerau-Levenshtein: {damerau_levenshtein_distance(word1, word2)}")
    print(f"  LCS-based:           {lcs_based_distance(word1, word2)}")
    
    # Transposition example
    print(f"\nTransposition example 'ab' vs 'ba':")
    print(f"  Levenshtein:         {weighted_edit_distance('ab', 'ba')}")
    print(f"  Damerau-Levenshtein: {damerau_levenshtein_distance('ab', 'ba')}")
    
    # One edit distance
    print(f"\nOne Edit Distance tests:")
    print(f"  'ab', 'acb': {is_one_edit_distance('ab', 'acb')}")  # True (insert)
    print(f"  'ab', 'a':   {is_one_edit_distance('ab', 'a')}")    # True (delete)
    print(f"  'ab', 'ac':  {is_one_edit_distance('ab', 'ac')}")   # True (replace)
    print(f"  'ab', 'ab':  {is_one_edit_distance('ab', 'ab')}")   # False (same)

Edit Distance Variations Comparison
Variant	Operations	Use Case	Complexity
Levenshtein	Insert, Delete, Replace	General spelling, DNA	O(nm)
Damerau-Levenshtein	Transposition	Typo correction	O(nm)
LCS-based	Insert, Delete only	Diff tools, version control	O(nm)
Hamming	Replace only (equal length)	Error correction codes	O(n)
Weighted	Custom costs per op	Domain-specific NLP	O(nm)

Real-World Applications

Edit distance is one of the most practically applied algorithms in computer science.

Spell Checking and Correction:

When you type "teh" and your editor suggests "the", edit distance is at work. The spell checker:

Detects "teh" isn't in the dictionary
Computes edit distance from "teh" to all dictionary words
Suggests words with smallest distances

Optimizations (like BK-trees) make this feasible for large dictionaries.

DNA Sequence Alignment:

In bioinformatics, comparing DNA sequences is fundamentally an edit distance problem. Researchers need to:

Find how similar two gene sequences are
Identify mutations (insertions, deletions, substitutions)
Align sequences for comparison

Variants like Needleman-Wunsch (global alignment) and Smith-Waterman (local alignment) extend edit distance with gap penalties.

Plagiarism Detection:

Diff Tools (Git, Unix diff):

Fuzzy Search:

Industry Applications

•Google Search: "Did you mean?" suggestions for misspelled queries
•Grammarly/Word: Real-time spelling and grammar correction
•BLAST (Bioinformatics): Sequence alignment for genomic research
•ElasticSearch: Fuzzy query matching in full-text search
•Git/Mercurial: Computing minimal diffs between commits
•OCR Systems: Correcting recognition errors in scanned text