Edit Distance Problem Levenshtein in DSA C++

Mental Model

Find the smallest number of changes needed to turn one word into another by adding, removing, or changing letters.

Analogy: Imagine you have two sentences written on paper and you want to make them the same by erasing, writing new letters, or changing letters one by one.

word1: c a t
word2: c a r

Positions:
 c -> a -> t
 c -> a -> r

We want to find how many edits to change 'cat' into 'car'.

Dry Run Walkthrough

Input: word1: "cat", word2: "car"

Goal: Find the minimum edits to change "cat" into "car"

Step 1: Compare last letters 't' and 'r', they differ, so consider substitution cost 1

Calculating edit distance for 'ca' and 'ca' plus 1 substitution

Why: Because last letters differ, substitution is one option

Step 2: Calculate edit distance for 'cat' and 'ca' by deleting 't' from word1

Calculating edit distance for 'ca' and 'car' plus 1 deletion

Why: Deleting last letter from word1 is another option

Step 3: Calculate edit distance for 'ca' and 'car' by inserting 'r' into word1

Calculating edit distance for 'cat' and 'ca' plus 1 insertion

Why: Inserting letter into word1 is the third option

Step 4: Compare results of substitution, deletion, insertion and pick minimum

Minimum edits is 1 (substitution)

Why: We want the smallest number of edits

Result:

Minimum edit distance = 1

Annotated Code

DSA C++

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

using namespace std;

int levenshteinDistance(const string &word1, const string &word2) {
    int m = word1.size();
    int n = word2.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

    // Initialize base cases: empty strings
    for (int i = 0; i <= m; ++i) dp[i][0] = i; // delete all chars from word1
    for (int j = 0; j <= n; ++j) dp[0][j] = j; // insert all chars to word1

    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (word1[i - 1] == word2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1]; // no edit needed
            } else {
                dp[i][j] = 1 + min({dp[i - 1][j],    // delete
                                    dp[i][j - 1],    // insert
                                    dp[i - 1][j - 1] // substitute
                                   });
            }
        }
    }
    return dp[m][n];
}

int main() {
    string word1 = "cat";
    string word2 = "car";
    int distance = levenshteinDistance(word1, word2);
    cout << "Minimum edit distance = " << distance << "\n";
    return 0;
}

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

initialize cost of deleting all characters from word1 to match empty word2

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

initialize cost of inserting all characters to empty word1 to match word2

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

no edit needed if characters match, carry over previous cost

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

choose minimum cost among delete, insert, substitute plus one edit

Output

Minimum edit distance = 1

Complexity Analysis

Time: O(m*n) because we fill a table of size m by n once

Space: O(m*n) because we store edit distances for all substring pairs

vs Alternative: Naive recursive approach repeats calculations causing exponential time; DP avoids this by storing results

Edge Cases

One or both strings empty

Distance equals length of the other string (all insertions or deletions)

DSA C++

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

Both strings identical

Distance is zero because no edits needed

DSA C++

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

Strings with repeated characters

Algorithm correctly counts edits considering repeated letters

DSA C++

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

When to Use This Pattern

When asked to find the minimum number of edits to convert one string into another, use the Levenshtein distance dynamic programming pattern because it efficiently counts insertions, deletions, and substitutions.

Common Mistakes

Mistake: Not initializing the first row and column of the DP table
Fix: Initialize dp[i][0] = i and dp[0][j] = j to handle empty string cases

Mistake: Confusing indices leading to off-by-one errors
Fix: Use i-1 and j-1 to access characters since dp table is 1-based for substrings

Summary

Calculates the minimum number of insertions, deletions, and substitutions to change one string into another.

Use when you need to measure how different two strings are or to correct typos automatically.

The key is building a table that stores solutions for smaller parts and combining them to solve the whole problem.

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