Edit Distance Problem Levenshtein in DSA Python

Mental Model

Find the smallest number of changes needed to turn one word into another by adding, removing, or changing letters.

Analogy: Imagine you have two sentences written on paper and you want to make them the same by erasing, writing new letters, or changing letters one by one.

word1: c a t
          ↑
word2: c a r
          ↑
Operations: replace 't' with 'r' to match

Dry Run Walkthrough

Input: word1: "cat", word2: "car"

Goal: Find the minimum number of edits to change "cat" into "car"

Step 1: Compare last letters 't' and 'r', they differ, so consider replace operation

Calculating cost for 'cat' vs 'car' -> replace 't' with 'r' cost = 1 + cost('ca' vs 'ca')

Why: We must fix the last letter difference by replacement or other edits

Step 2: Compare 'ca' vs 'ca', letters match, no edit needed

Cost('ca' vs 'ca') = cost('c' vs 'c') + cost('a' vs 'a') = 0

Why: Matching letters do not add to edit distance

Step 3: Calculate final cost as 1 (for replacing 't' with 'r') + 0 (previous matches)

Edit distance = 1

Why: Only one replacement needed to make words equal

Result:

Edit distance matrix final cell = 1
Minimum edits needed: 1

Annotated Code

DSA Python

class EditDistance:
    def __init__(self, word1: str, word2: str):
        self.word1 = word1
        self.word2 = word2

    def compute(self) -> int:
        m, n = len(self.word1), len(self.word2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]

        for i in range(m + 1):
            dp[i][0] = i  # cost of deleting all letters from word1
        for j in range(n + 1):
            dp[0][j] = j  # cost of inserting all letters to word1

        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if self.word1[i - 1] == self.word2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1]  # letters match, no edit
                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]

if __name__ == '__main__':
    ed = EditDistance("cat", "car")
    print(f"Minimum edits needed: {ed.compute()}")

dp = [[0] * (n + 1) for _ in range(m + 1)]

Initialize matrix to store edit distances for all prefixes

for i in range(m + 1): dp[i][0] = i

Cost to delete all letters from word1 to match empty word2

for j in range(n + 1): dp[0][j] = j

Cost to insert all letters to empty word1 to match word2

if self.word1[i - 1] == self.word2[j - 1]: dp[i][j] = dp[i - 1][j - 1]

No edit needed if letters match

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

Choose minimum cost among delete, insert, replace plus one edit

Output

Minimum edits needed: 1

Complexity Analysis

Time: O(m*n) because we fill a matrix of size m by n once

Space: O(m*n) because we store edit distances for all prefix pairs

vs Alternative: Naive recursive approach has exponential time due to repeated subproblems; dynamic programming reduces it to polynomial time

Edge Cases

One or both words are empty strings

Edit distance equals length of the other word (all insertions or deletions)

DSA Python

for i in range(m + 1): dp[i][0] = i

Words are identical

Edit distance is zero since no edits are needed

DSA Python

if self.word1[i - 1] == self.word2[j - 1]: dp[i][j] = dp[i - 1][j - 1]

Words differ completely

Edit distance equals length of longer word (all replacements or insertions/deletions)

DSA Python

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

When to Use This Pattern

When asked to find the minimum number of changes to convert one string into another, use the Edit Distance pattern with dynamic programming to efficiently compute the answer.

Common Mistakes

Mistake: Not initializing the first row and column of the dp matrix correctly
Fix: Set dp[i][0] = i and dp[0][j] = j to represent base cases of empty strings

Mistake: Forgetting to add 1 when counting an edit operation
Fix: Add 1 to the minimum of delete, insert, replace costs to count the current edit

Mistake: Confusing indices when accessing characters in the strings
Fix: Use i-1 and j-1 to access characters because dp matrix includes empty prefix at index 0

Summary

Calculates the minimum number of insertions, deletions, and replacements to convert one word into another.

Use when you need to measure how different two strings are or find the minimal edits to transform one into the other.

The key insight is to build a matrix of solutions for smaller prefixes and use them to solve bigger problems efficiently.

Practice

1. What does the Edit Distance (Levenshtein distance) between two strings measure?

easy

A. The minimum number of single-character edits to change one string into the other

B. The number of common characters between two strings

C. The length of the longest common substring

D. The number of characters in the longer string

Solution

1. Step 1: Understand the definition of Edit Distance

   Edit Distance counts how many changes (insert, delete, replace) are needed to convert one string to another.

2. Step 2: Compare options with definition

   Only The minimum number of single-character edits to change one string into the other correctly describes this minimum number of single-character edits.

3. Final Answer:

   The minimum number of single-character edits to change one string into the other -> Option A

4. Quick Check:

   Edit Distance = minimum edits [OK]

Hint: Edit Distance counts minimal edits to match strings [OK]

Common Mistakes:

• Confusing with longest common substring
• Thinking it counts common characters
• Assuming it measures string length

2. Which of the following Python code snippets correctly initializes a 2D list for dynamic programming of size (m+1) x (n+1)?

easy

A. dp = [0] * (m+1) * (n+1)

B. dp = [[0] * (n+1) for _ in range(m+1)]

C. dp = [[0] * m for _ in range(n)]

D. dp = [[0] * (m+1)] * (n+1)

Solution

1. Step 1: Understand 2D list initialization in Python

   Using list comprehension with separate inner lists avoids shared references.

2. Step 2: Analyze each option

   dp = [[0] * (n+1) for _ in range(m+1)] correctly creates independent rows. dp = [[0] * (m+1)] * (n+1) creates shallow copies causing bugs. Options A and C have wrong dimensions or types.

3. Final Answer:

   dp = [[0] * (n+1) for _ in range(m+1)] -> Option B

4. Quick Check:

   Proper 2D list init = dp = [[0] * (n+1) for _ in range(m+1)] [OK]

Hint: Use list comprehension for 2D lists to avoid shared rows [OK]

Common Mistakes:

• Using multiplication for 2D lists causing shared references
• Mixing up m and n dimensions
• Creating 1D list instead of 2D

3. What is the output of the following Python code snippet that calculates the Levenshtein distance between 'kitten' and 'sitting'?

def levenshtein(s1, s2):
    m, n = len(s1), len(s2)
    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 s1[i-1] == s2[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]

print(levenshtein('kitten', 'sitting'))

medium

A. 4

B. 5

C. 3

D. 6

Solution

1. Step 1: Understand the Levenshtein distance calculation

   Compare 'kitten' and 'sitting' stepwise counting minimal edits: substitute 'k'->'s' (kitten -> sitten), substitute 'e'->'i' (sitten -> sittin), insert 'g' at end (sittin -> sitting). Total 3 edits.

2. Step 2: Verify with code logic

   The code correctly implements the DP approach and returns dp[m][n] which is 3 for these inputs.

3. Final Answer:

   3 -> Option C

4. Quick Check:

   Levenshtein('kitten','sitting') = 3 [OK]

Hint: Count minimal edits: replace, insert, delete [OK]

Common Mistakes:

• Counting only replacements, ignoring insertions
• Miscounting characters to change
• Confusing with substring length

4. Identify the bug in this Levenshtein distance code snippet:

def levenshtein_bug(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n+1)] * (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 s1[i-1] == s2[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]

medium

A. Using dp = [[0] * (n+1)] * (m+1) causes all rows to reference the same list

B. The loops should start from 0 instead of 1

C. The condition s1[i-1] == s2[j-1] should be s1[i] == s2[j]

D. The return statement should be dp[0][0]

Solution

1. Step 1: Analyze dp initialization

   Using multiplication to create dp causes all rows to point to the same list, so updating one row updates all rows.

2. Step 2: Understand impact on algorithm

   This shared reference breaks the DP table updates, causing incorrect results.

3. Final Answer:

   Using dp = [[0] * (n+1)] * (m+1) causes all rows to reference the same list -> Option A

4. Quick Check:

   Shared row references cause bugs [OK]

Hint: Avoid list multiplication for 2D lists; use list comprehension [OK]

Common Mistakes:

• Using wrong dp initialization
• Incorrect loop ranges
• Wrong indexing in condition

5. Given two strings s1 = 'intention' and s2 = 'execution', what is the minimum edit distance using Levenshtein algorithm? Consider insert, delete, and replace operations each cost 1.

hard

A. 7

B. 5

C. 4

D. 6

Solution

1. Step 1: Compare strings and count minimal edits

   Transform 'intention' to 'execution' requires the minimum number of single-character edits (insertions, deletions, substitutions) of 6.

2. Step 2: Confirm with Levenshtein DP logic

   Dynamic programming confirms minimum edits as 6 for these strings.

3. Final Answer:

   6 -> Option D

4. Quick Check:

   Levenshtein('intention','execution') = 6 [OK]

Hint: Count replacements and insertions carefully for longer strings [OK]

Common Mistakes:

• Underestimating number of replacements
• Ignoring insertions
• Confusing with Hamming distance