Edit Distance Problem Levenshtein in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Levenshtein Distance Calculation

What is the output of the following Python code that calculates the Levenshtein distance between two strings?

DSA Python

def levenshtein(s1, s2):
    if len(s1) < len(s2):
        return levenshtein(s2, s1)
    if len(s2) == 0:
        return len(s1)
    previous_row = range(len(s2) + 1)
    for i, c1 in enumerate(s1):
        current_row = [i + 1]
        for j, c2 in enumerate(s2):
            insertions = previous_row[j + 1] + 1
            deletions = current_row[j] + 1
            substitutions = previous_row[j] + (c1 != c2)
            current_row.append(min(insertions, deletions, substitutions))
        previous_row = current_row
    return previous_row[-1]

print(levenshtein("kitten", "sitting"))

A 2

B 4

C 3

D 5

💡 Hint

Think about the minimum number of edits (insertions, deletions, substitutions) to convert 'kitten' to 'sitting'.

The Levenshtein distance between 'kitten' and 'sitting' is 3: substitute 'k' with 's', substitute 'e' with 'i', and insert 'g' at the end.

🧠 Conceptual

intermediate

Understanding Levenshtein Distance Operations

Which of the following operations are considered when calculating the Levenshtein distance between two strings?

A Insertion, Deletion, Substitution

B Insertion, Deletion, Transposition

C Substitution, Transposition, Reversal

D Insertion, Reversal, Duplication

💡 Hint

Levenshtein distance counts the minimal number of single-character edits.

Levenshtein distance counts insertions, deletions, and substitutions only. Transposition is not counted in Levenshtein but in other distances like Damerau-Levenshtein.

🔧 Debug

advanced

Identify the Error in Levenshtein Distance Code

What error will the following code raise when executed?

DSA Python

def levenshtein_bug(s1, s2):
    previous_row = [0] * (len(s2) + 1)
    for i, c1 in enumerate(s1):
        current_row = [i + 1]
        for j, c2 in enumerate(s2):
            insertions = previous_row[j + 1] + 1
            deletions = current_row[j] + 1
            substitutions = previous_row[j] + (c1 != c2)
            current_row.append(min(insertions, deletions, substitutions))
        previous_row = current_row
    return previous_row[-1]

print(levenshtein_bug("abc", ""))

A TypeError

B IndexError

C 0

D NameError

💡 Hint

Check how previous_row is initialized and accessed when s2 is empty.

When s2 is empty, previous_row has length 1. Accessing previous_row[j + 1] with j=0 causes IndexError.

🚀 Application

advanced

Minimum Edit Distance for Spell Correction

Given the words 'flaw' and 'lawn', what is the minimum edit distance calculated by the Levenshtein algorithm?

A 4

B 3

C 1

D 2

💡 Hint

Consider the minimal edits to convert 'flaw' into 'lawn'.

The minimal edits are: delete 'f' and substitute 'w' with 'n', total 2 edits.

❓ Predict Output

expert

Output of Levenshtein Distance with Unicode Characters

What is the output of this code calculating Levenshtein distance between two Unicode strings?

DSA Python

def levenshtein_unicode(s1, s2):
    if len(s1) < len(s2):
        return levenshtein_unicode(s2, s1)
    if len(s2) == 0:
        return len(s1)
    previous_row = range(len(s2) + 1)
    for i, c1 in enumerate(s1):
        current_row = [i + 1]
        for j, c2 in enumerate(s2):
            insertions = previous_row[j + 1] + 1
            deletions = current_row[j] + 1
            substitutions = previous_row[j] + (c1 != c2)
            current_row.append(min(insertions, deletions, substitutions))
        previous_row = current_row
    return previous_row[-1]

print(levenshtein_unicode("café", "café"))

A 1

B 0

C 2

D 3

💡 Hint

Note that the second string uses 'e' plus combining accent, which is two characters.

The strings differ by one character because 'é' in first string is a single character, while in second string it's 'e' plus combining accent, so distance is 1.

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