Edit Distance Problem Levenshtein in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Levenshtein Distance Calculation

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

DSA C++

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

int levenshteinDistance(const std::string& s1, const std::string& s2) {
    int m = s1.size();
    int n = s2.size();
    std::vector<std::vector<int>> dp(m + 1, std::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 (s1[i - 1] == s2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = 1 + std::min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]});
            }
        }
    }
    return dp[m][n];
}

int main() {
    std::string a = "kitten";
    std::string b = "sitting";
    std::cout << levenshteinDistance(a, b) << std::endl;
    return 0;
}

A 3

B 4

C 2

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'
• 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, Reversal, Deletion

B Insertion, Deletion, Substitution

C Substitution, Transposition, Reversal

D Insertion, Deletion, Transposition

💡 Hint

Levenshtein distance counts the minimum edits needed using three basic operations.

Levenshtein distance uses insertion, deletion, and substitution operations only. Transposition is not included.

🔧 Debug

advanced

Identify the Bug in Levenshtein Distance Code

What error will the following C++ code produce when calculating Levenshtein distance?

DSA C++

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

int levenshteinDistance(const std::string& s1, const std::string& s2) {
    int m = s1.size();
    int n = s2.size();
    std::vector<std::vector<int>> dp(m, std::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 (s1[i - 1] == s2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = 1 + std::min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]});
            }
        }
    }
    return dp[m][n];
}

int main() {
    std::cout << levenshteinDistance("abc", "yabd") << std::endl;
    return 0;
}

A Returns incorrect distance value 0

B Compilation error due to missing header

C std::out_of_range exception due to invalid vector access

D Runs correctly and outputs 2

💡 Hint

Check the size of the dp vector and the loop boundaries.

The dp vector is initialized with size m x n, but loops run up to m and n inclusive, causing out-of-range access.

❓ Predict Output

advanced

Levenshtein Distance Matrix Final State

What is the final state of the dp matrix after running the Levenshtein distance algorithm on strings "abc" and "yabd"?

DSA C++

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

int main() {
    std::string s1 = "abc";
    std::string s2 = "yabd";
    int m = s1.size();
    int n = s2.size();
    std::vector<std::vector<int>> dp(m + 1, std::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 (s1[i - 1] == s2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = 1 + std::min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]});
            }
        }
    }

    for (int i = 0; i <= m; ++i) {
        for (int j = 0; j <= n; ++j) {
            std::cout << dp[i][j] << " ";
        }
        std::cout << std::endl;
    }
    return 0;
}

A [[0,1,2,3,4],[1,1,1,2,3],[2,2,2,1,2],[3,3,3,2,2]]

B [[0,1,2,3,4],[1,1,2,3,4],[2,2,1,2,3],[3,3,3,2,3]]

C [[0,1,2,3,4],[1,1,2,3,4],[2,2,1,2,3],[3,3,2,3,4]]

D [[0,1,2,3,4],[1,1,2,3,4],[2,2,2,2,3],[3,3,2,2,3]]

💡 Hint

Trace the matrix row by row considering matches and minimum edits.

The dp matrix shows the minimum edit distances for substrings. The final matrix is:

0 1 2 3 4
1 1 1 2 3
2 2 2 1 2
3 3 3 2 2

🚀 Application

expert

Minimum Edit Distance for Large Strings

Given two strings each of length 1000, what is the time complexity of the classic dynamic programming solution to compute the Levenshtein distance?

A O(n log n)

B O(2^n)

C O(n)

D O(n^2)

💡 Hint

Consider the size of the dp matrix and the nested loops.

The classic Levenshtein distance algorithm uses a matrix of size n x n and fills it with nested loops, resulting in O(n^2) time complexity.

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