Edit Distance Problem Levenshtein in DSA C++ - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the base case for the DP table.

DSA C++

for (int i = 0; i <= m; i++) dp[i][0] = [1];

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

An

B0

Cm

Di

Attempts:

3 left

💡 Hint

Common Mistakes

Setting dp[i][0] to 0 instead of i.

Using the wrong variable like m or n instead of i.

The base case for transforming a string of length i to an empty string requires i deletions, so dp[i][0] = i.

2fill in blank

medium

Complete the code to check if characters at position i-1 and j-1 are equal.

DSA C++

if (word1[i - 1] [1] word2[j - 1]) dp[i][j] = dp[i - 1][j - 1];

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

A!=

B==

C>

D<

Attempts:

3 left

💡 Hint

Common Mistakes

Using '!=' instead of '=='.

Using comparison operators like '>' or '<' which are incorrect here.

If the characters are equal, no operation is needed, so dp[i][j] equals dp[i-1][j-1].

3fill in blank

hard

Fix the error in the code to compute the minimum edit distance with insert, delete, and replace operations.

DSA C++

dp[i][j] = 1 + std::min({dp[i - 1][j], dp[i][j - 1], [1]);

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

Adp[i - 1][j - 1]

Bdp[i][j]

Cdp[i - 1][j + 1]

Ddp[i + 1][j - 1]

Attempts:

3 left

💡 Hint

Common Mistakes

Using dp[i][j] which causes infinite recursion.

Using indices out of bounds like dp[i-1][j+1].

The replace operation cost is dp[i-1][j-1], so it must be included in the minimum calculation.

4fill in blank

hard

Fill both blanks to complete the nested loops iterating over the DP table.

DSA C++

for (int [1] = 1; [1] <= m; [1]++) {
    for (int [2] = 1; [2] <= n; [2]++) {

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

Ai

Bj

Ck

Dx

Attempts:

3 left

💡 Hint

Common Mistakes

Using the same variable name for both loops.

Using uncommon variable names that confuse readers.

The standard variable names for rows and columns in DP are i and j respectively.

5fill in blank

hard

Fill all three blanks to complete the function signature and return statement.

DSA C++

int [1](const std::string& word1, const std::string& word2) {
    int m = word1.size(), n = word2.size();
    std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1));
    // ... DP logic ...
    return [2][[3]][n];
}

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

AeditDistance

Bdp

Cm

Dword1

Attempts:

3 left

💡 Hint

Common Mistakes

Returning dp[n][m] instead of dp[m][n].

Using wrong function name or variable names.

The function is named editDistance, returns dp[m][n] which holds the final answer.

Practice

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

easy

A. The minimum number of insertions, deletions, or substitutions to convert one string into another

B. The number of matching characters in the same positions

C. The length difference between two strings

D. The maximum number of characters that differ between two strings

Solution

1. Step 1: Understand the definition of Edit Distance

   Edit Distance counts how many changes are needed to make two strings equal.

2. Step 2: Identify allowed operations

   Allowed operations are insertion, deletion, and substitution of characters.

3. Final Answer:

   The minimum number of insertions, deletions, or substitutions to convert one string into another -> Option A

4. Quick Check:

   Edit Distance = minimum edits needed [OK]

Hint: Think of edits needed to match strings exactly [OK]

Common Mistakes:

• Confusing edit distance with matching characters count
• Ignoring substitution as an allowed operation
• Thinking it measures only length difference

2. Which of the following is the correct way to initialize the base case for the DP table in Levenshtein distance calculation in C++?

easy

A. for (int i = 0; i <= m; i++) dp[i][0] = i;

B. for (int j = 0; j <= n; j++) dp[0][j] = 0;

C. dp[0][0] = 1;

D. for (int i = 1; i <= m; i++) dp[i][0] = 0;

Solution

1. Step 1: Understand base case meaning

   dp[i][0] means converting first i characters of string1 to empty string, so requires i deletions.

2. Step 2: Identify correct initialization

   Setting dp[i][0] = i correctly counts deletions needed for empty second string.

3. Final Answer:

   for (int i = 0; i <= m; i++) dp[i][0] = i; -> Option A

4. Quick Check:

   Base case rows = index count [OK]

Hint: Base case dp[i][0] = i for deletions [OK]

Common Mistakes:

• Initializing dp[0][j] incorrectly to zero
• Starting loops from 1 instead of 0
• Setting dp[0][0] to 1 instead of 0

3. What is the output of the following C++ code snippet that calculates the Levenshtein distance between "kitten" and "sitting"?

int levenshteinDistance(const string &s, const string &t) {
    int m = s.size(), n = t.size();
    vector dp(m + 1, vector<int>(n + 1));
    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s[i - 1] == t[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];
}

cout << levenshteinDistance("kitten", "sitting") << endl;

medium

A. 4

B. 6

C. 5

D. 3

Solution

1. Step 1: Understand the strings and operations

   "kitten" to "sitting" requires substitutions and insertions.

2. Step 2: Calculate minimum edits

   Substitute 'k'->'s', substitute 'e'->'i', insert 'g' at end, total 3 edits.

3. Final Answer:

   3 -> Option D

4. Quick Check:

   Levenshtein distance("kitten", "sitting") = 3 [OK]

Hint: Count substitutions + insertions needed [OK]

Common Mistakes:

• Counting only substitutions, ignoring insertions
• Misaligning indices causing off-by-one errors
• Confusing Levenshtein with Hamming distance

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

int levenshteinDistance(string s, string t) {
    int m = s.size(), n = t.size();
    vector dp(m, vector<int>(n));
    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s[i - 1] == t[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. The return statement should be dp[m-1][n-1]

B. The dp vector is initialized with size m x n instead of (m+1) x (n+1)

C. The loops should start from 0 instead of 1

D. The comparison s[i] == t[j] is incorrect

Solution

1. Step 1: Check dp vector initialization

   dp must have size (m+1) x (n+1) to include base cases for empty strings.

2. Step 2: Identify impact of wrong size

   With size m x n, accessing dp[m][0] or dp[0][n] causes out-of-bounds errors.

3. Final Answer:

   The dp vector is initialized with size m x n instead of (m+1) x (n+1) -> Option B

4. Quick Check:

   dp size must be (m+1) x (n+1) [OK]

Hint: dp size must cover empty string cases [OK]

Common Mistakes:

• Forgetting to add +1 to dp dimensions
• Returning dp[m][n] without proper dp size
• Incorrect loop ranges causing index errors

5. Given two strings "intention" and "execution", what is the minimum edit distance using Levenshtein algorithm? Show the reasoning for each step.

hard

A. 7

B. 5

C. 6

D. 8

Solution

1. Step 1: Analyze character differences

   Compare "intention" and "execution" character by character, counting edits needed.

2. Step 2: Calculate minimal edits

   The optimal alignment requires 6 edits: substitutions, insertions, and deletions to match exactly.

3. Final Answer:

   6 -> Option C

4. Quick Check:

   Levenshtein distance("intention", "execution") = 6 [OK]

Hint: Count substitutions and insertions carefully [OK]

Common Mistakes:

• Ignoring insertions or deletions
• Miscounting substitutions
• Assuming only substitutions needed