Edit Distance Problem Levenshtein in DSA C++ - Build from Scratch

Edit Distance Problem Levenshtein

📖 Scenario: You are building a simple spell checker that compares two words and finds how many changes are needed to convert one word into the other. This helps suggest corrections for typos.

🎯 Goal: Calculate the Levenshtein edit distance between two given words using dynamic programming in C++. This distance tells how many single-character edits (insertions, deletions, or substitutions) are needed to change one word into the other.

📋 What You'll Learn

Create two string variables with exact values

Create a 2D vector to store distances

Use nested loops to fill the distance table using Levenshtein logic

Print the final edit distance value

💡 Why This Matters

🌍 Real World

Spell checkers, DNA sequence analysis, and natural language processing use edit distance to find how similar two strings are.

💼 Career

Understanding dynamic programming and string algorithms is essential for software engineering roles involving text processing, search engines, and bioinformatics.

1

Create the input strings

Create two string variables called word1 and word2 with the exact values "kitten" and "sitting" respectively.

DSA C++

// Your code here

Hint

Use string word1 = "kitten"; and string word2 = "sitting"; to create the two words.

2

Create the distance table

Create a 2D vector of integers called dp with size (word1.length() + 1) rows and (word2.length() + 1) columns. Initialize all values to zero.

DSA C++

#include 
#include 
#include 

using namespace std;

int main() {
    string word1 = "kitten";
    string word2 = "sitting";

    // Create dp vector here

    return 0;
}

Hint

Use vector> dp(word1.length() + 1, vector(word2.length() + 1, 0)); to create the 2D table.

3

Fill the distance table with Levenshtein logic

Use two for loops with variables i from 0 to word1.length() and j from 0 to word2.length(). Initialize the first row and first column of dp with i and j respectively. Then fill the rest of dp using the rules: if characters match, copy diagonal value; else take 1 plus minimum of left, top, and diagonal neighbors.

DSA C++

#include 
#include 
#include 

using namespace std;

int main() {
    string word1 = "kitten";
    string word2 = "sitting";

    vector> dp(word1.length() + 1, vector(word2.length() + 1, 0));

    // Fill dp table here

    return 0;
}

Hint

Initialize first row and column with indices. Use nested loops to fill dp. If characters match, copy diagonal. Else add 1 plus minimum of left, top, diagonal.

4

Print the final edit distance

Print the value of dp[word1.length()][word2.length()] which is the Levenshtein edit distance between word1 and word2.

DSA C++

#include 
#include 
#include 
#include 

using namespace std;

int main() {
    string word1 = "kitten";
    string word2 = "sitting";

    vector> dp(word1.length() + 1, vector(word2.length() + 1, 0));

    for (int i = 0; i <= word1.length(); i++) {
        dp[i][0] = i;
    }
    for (int j = 0; j <= word2.length(); j++) {
        dp[0][j] = j;
    }

    for (int i = 1; i <= word1.length(); i++) {
        for (int j = 1; j <= word2.length(); j++) {
            if (word1[i - 1] == word2[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]});
            }
        }
    }

    // Print the edit distance below

    return 0;
}

Hint

Use cout << dp[word1.length()][word2.length()] << endl; to print the final edit distance.

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