Edit distance (Levenshtein) in NLP - Interactive Code Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the edit distance matrix with zeros.

NLP

def levenshtein_distance(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[[1] for _ in range(n + 1)] for _ in range(m + 1)]
    return dp

Drag options to blanks, or click blank then click option'

A''

B0

CNone

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Initializing with 1 instead of 0 causes incorrect distance calculations.

Using None or empty string leads to type errors later.

The matrix for edit distance is initialized with zeros to start the dynamic programming table.

2fill in blank

medium

Complete the code to set the first row of the matrix representing insertions.

NLP

def levenshtein_distance(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
    for j in range(n + 1):
        dp[0][j] = [1]
    return dp[0]

Drag options to blanks, or click blank then click option'

Am

B0

C1

Dj

Attempts:

3 left

💡 Hint

Common Mistakes

Setting all values to 0 ignores insertion costs.

Using m instead of j confuses rows and columns.

The first row represents the cost of inserting characters, so dp[0][j] = j.

3fill in blank

hard

Fix the error in the condition to check if characters are the same.

NLP

if s1[i - 1] [1] s2[j - 1]:
    cost = 0
else:
    cost = 1

Drag options to blanks, or click blank then click option'

A==

B<

C!=

D>

Attempts:

3 left

💡 Hint

Common Mistakes

Using '!=' reverses the logic and causes wrong cost calculation.

Using '<' or '>' is invalid for character equality check.

We check if characters are equal with '=='. If equal, cost is zero.

4fill in blank

hard

Fill both blanks to compute the minimum edit distance step.

NLP

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

Drag options to blanks, or click blank then click option'

A1

B0

Ccost

D2

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 for insertion or deletion cost ignores actual cost.

Using cost instead of 1 confuses substitution cost with insertion/deletion.

Insertion and deletion each cost 1, so add 1 to those steps.

5fill in blank

hard

Fill all three blanks to complete the Levenshtein distance function.

NLP

def levenshtein_distance(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = [1]
    for j in range(n + 1):
        dp[0][j] = [2]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            cost = 0 if s1[i - 1] [3] s2[j - 1] else 1
            dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + cost)
    return dp[m][n]

Drag options to blanks, or click blank then click option'

Ai

Bj

C==

D!=

Attempts:

3 left

💡 Hint

Common Mistakes

Mixing up i and j in initialization causes wrong matrix setup.

Using '!=' instead of '==' reverses substitution cost logic.

First column is initialized with i (deletions), first row with j (insertions), and character equality checked with '=='.