Edit Distance Problem Levenshtein in DSA C++ - Deep Dive

Overview - Edit Distance Problem Levenshtein

What is it?

Edit Distance, also called Levenshtein distance, measures how many changes it takes to turn one word into another. Changes include adding, removing, or changing a letter. It helps computers understand how similar two words are. This is useful in spell checkers, DNA analysis, and text comparison.

Why it matters

Without edit distance, computers would struggle to find similar words or correct typos automatically. It solves the problem of measuring similarity between strings in a clear way. This helps in search engines, language translation, and error correction, making technology smarter and more user-friendly.

Where it fits

Before learning edit distance, you should understand strings and basic loops. After this, you can learn dynamic programming and advanced string algorithms like longest common subsequence or approximate pattern matching.

Mental Model

Core Idea

Edit distance counts the smallest number of letter changes needed to turn one word into another.

Think of it like...

Imagine you have two sentences written on paper, and you want to make one look exactly like the other by erasing, writing, or changing letters. The edit distance is how many times you need to do these actions.

  Word1: s i t t i n g
  Word2: k i t t e n

  Steps:
  s -> k (substitute)
  i -> i (no change)
  t -> t (no change)
  t -> t (no change)
  i -> e (substitute)
  n -> n (no change)
  g -> (delete)

  Total edits = 3

Build-Up - 7 Steps

1

Foundation

Understanding Basic String Operations

Concept: Learn the three basic operations: insert, delete, and substitute characters in strings.

To change one word into another, you can: - Insert a letter (add a new letter anywhere) - Delete a letter (remove a letter) - Substitute a letter (change one letter to another) Each operation counts as one edit.

Result

You can now think about how to transform one word into another using these simple steps.

Knowing these three operations is essential because edit distance measures the minimum number of these needed to convert one string to another.

2

Foundation

What is Edit Distance Exactly?

Concept: Edit distance is the smallest number of edits needed to change one string into another.

For example, changing 'cat' to 'cut' requires one substitution (a -> u). Changing 'cat' to 'cats' requires one insertion (add s). Changing 'cat' to 'at' requires one deletion (remove c). The edit distance is the minimum count of these operations.

Result

You understand that edit distance is a number representing how different two words are.

This step connects the basic operations to a measurable quantity, making the problem concrete.

3

Intermediate

Dynamic Programming Approach Introduction

🤔Before reading on: do you think checking all possible edits one by one is efficient or inefficient? Commit to your answer.

Concept: Use a table to store results of smaller problems to avoid repeating work.

We create a 2D table where rows represent letters of the first word and columns represent letters of the second word. Each cell shows the edit distance between prefixes of the two words. We fill the table using these rules: - If letters match, take diagonal value (no new edit) - Else, take 1 + minimum of (left, top, diagonal) cells representing insert, delete, substitute respectively.

Result

A filled table that shows the minimum edits needed for every prefix pair of the two words.

Using a table to remember past results saves time and makes the problem solvable efficiently.

4

Intermediate

Implementing Levenshtein Distance in C++

🤔Before reading on: do you think the table size depends on the length of both words or just one? Commit to your answer.

Concept: Write code that builds and fills the table to find the edit distance.

We create a vector of vectors (2D array) sized (m+1) x (n+1) where m and n are lengths of the two words. Initialize first row and column with incremental values (distance from empty string). Fill the rest using the rules: 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]) Return dp[m][n] as the answer.

Result

The code outputs the minimum edit distance between the two input words.

Knowing how to translate the problem into code with a table is key to solving many string comparison problems.

5

Intermediate

Tracing the DP Table with an Example

🤔Before reading on: do you think the edit distance between 'kitten' and 'sitting' is more or less than 4? Commit to your answer.

Concept: Walk through the table filling process step-by-step with real words.

Words: 'kitten' and 'sitting' Create a 7x8 table (lengths + 1) Fill first row and column with 0 to length values. Fill each cell by comparing letters and choosing minimum edits. At the end, dp[6][7] gives the edit distance. The final answer is 3.

Result

The table shows the minimum edits needed at each step, confirming the final edit distance is 3.

Seeing the table fill in real time helps understand how the algorithm builds up the solution.

6

Advanced

Optimizing Space Usage in Edit Distance

🤔Before reading on: do you think we need to keep the entire table in memory or just part of it? Commit to your answer.

Concept: Reduce memory by storing only necessary rows instead of the full table.

Notice that to fill row i, we only need row i-1. Use two 1D arrays instead of a 2D array. Update arrays row by row, overwriting old data. This reduces space from O(m*n) to O(min(m,n)).

Result

The algorithm uses less memory but still computes the correct edit distance.

Understanding dependencies in the table allows memory optimization, important for large inputs.

7

Expert

Handling Weighted Edit Operations and Extensions

🤔Before reading on: do you think all edits must cost the same? Commit to your answer.

Concept: Extend the algorithm to handle different costs for insert, delete, and substitute operations.

Assign different weights to each operation (e.g., substitution might cost more). Modify the DP formula to add the specific cost instead of 1. This allows modeling real-world scenarios like keyboard typos or DNA mutations. Also, extensions include Damerau-Levenshtein distance which counts transpositions.

Result

The algorithm can now compute more realistic edit distances reflecting actual error costs.

Knowing how to customize costs makes the edit distance more flexible and applicable to complex problems.

Under the Hood

The algorithm builds a matrix where each cell represents the minimum edits to convert prefixes of the two strings. It uses dynamic programming to reuse previously computed results, avoiding repeated work. The matrix is filled row by row, using the minimum of three possible operations: insert, delete, or substitute. This bottom-up approach ensures the final cell contains the total minimum edits.

Why designed this way?

Early naive methods tried all possible edit sequences, which is exponential and slow. Dynamic programming was introduced to break the problem into smaller overlapping subproblems and store their results. This design balances time and space efficiency, making the problem solvable in polynomial time. Alternatives like recursive brute force were rejected due to inefficiency.

┌─────────────┬─────┬─────┬─────┬─────┐
│             │ ''  │ s   │ i   │ t   │
├─────────────┼─────┼─────┼─────┼─────┤
│ ''          │ 0   │ 1   │ 2   │ 3   │
│ k           │ 1   │ 1   │ 2   │ 3   │
│ i           │ 2   │ 2   │ 1   │ 2   │
│ t           │ 3   │ 3   │ 2   │ 1   │
│ t           │ 4   │ 4   │ 3   │ 2   │
│ e           │ 5   │ 5   │ 4   │ 3   │
│ n           │ 6   │ 6   │ 5   │ 4   │
└─────────────┴─────┴─────┴─────┴─────┘
Each cell dp[i][j] shows minimum edits to convert first i letters of word1 to first j letters of word2.

Myth Busters - 4 Common Misconceptions

Quick: Does edit distance only count substitutions? Commit to yes or no.

Common Belief: Edit distance counts only letter substitutions between words.

Reality: Edit distance counts insertions, deletions, and substitutions equally as edits.

Why it matters: Ignoring insertions and deletions leads to wrong similarity measures and poor spell checking.

Quick: Is the edit distance always symmetric? Commit to yes or no.

Common Belief: Edit distance from word A to B is always the same as from B to A.

Reality: Standard Levenshtein distance is symmetric, but weighted or variant distances may not be.

Why it matters: Assuming symmetry can cause errors in algorithms that rely on direction, like certain search heuristics.

Quick: Does a zero edit distance mean words are identical? Commit to yes or no.

Common Belief: If edit distance is zero, the two words are exactly the same.

Reality: Yes, zero edit distance means identical strings with no edits needed.

Why it matters: This is a true fact, but sometimes people confuse zero distance with similar words, which is incorrect.

Quick: Can edit distance be computed efficiently without dynamic programming? Commit to yes or no.

Common Belief: You can compute edit distance quickly by checking all possible edits directly.

Reality: Naive methods are exponential and impractical; dynamic programming is needed for efficiency.

Why it matters: Trying naive methods on large inputs causes huge slowdowns and crashes.

Expert Zone

1

The choice of operation costs can drastically change the meaning of edit distance in applications like bioinformatics.

2

Optimizing space by using only two rows is common, but further optimization is possible with Hirschberg's algorithm to recover the edit sequence.

3

Damerau-Levenshtein distance adds transposition as a single edit, which better models common human typing errors.

When NOT to use

Edit distance is not suitable when you need to compare very long texts efficiently; in such cases, hashing or fingerprinting methods like MinHash are better. Also, for semantic similarity, edit distance is insufficient; natural language processing techniques are preferred.

Production Patterns

In spell checkers, edit distance is used to suggest corrections by finding dictionary words within a small edit distance. In DNA analysis, weighted edit distances model mutation costs. Search engines use approximate matching with edit distance to handle typos.

Connections

Dynamic Programming

Edit distance is a classic example solved by dynamic programming.

Understanding edit distance deepens comprehension of dynamic programming's power to solve problems by breaking them into overlapping subproblems.

Hamming Distance

Both measure string differences but Hamming distance counts only substitutions for equal-length strings.

Knowing the difference helps choose the right metric: Hamming for fixed-length, edit distance for variable-length comparisons.

Genetic Mutation Analysis

Edit distance models mutations in DNA sequences as insertions, deletions, and substitutions.

This cross-domain link shows how a computer science concept helps understand biological evolution and disease.

Common Pitfalls

#1 Confusing the order of strings and expecting different results.

Wrong approach:

int dist = levenshteinDistance(word1, word2);
int distReverse = levenshteinDistance(word2, word1);
// Assume dist != distReverse

Correct approach:

int dist = levenshteinDistance(word1, word2);
int distReverse = levenshteinDistance(word2, word1);
// Both should be equal for standard Levenshtein

Root cause:

Misunderstanding that standard edit distance is symmetric and order does not affect the result.

#2 Not initializing the first row and column of the DP table correctly.

Wrong approach:

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

Correct approach:

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

Root cause:

Failing to set base cases causes incorrect edit distance calculations.

#3 Using recursion without memoization leading to exponential time.

Wrong approach:

int dist(string s1, string s2) {
if (s1.empty()) return s2.length();
if (s2.empty()) return s1.length();
// recursive calls without caching
}

Correct approach:

Use a DP table or memoization to store intermediate results and avoid repeated work.

Root cause:

Not applying dynamic programming leads to inefficient and slow solutions.

Key Takeaways

Edit distance measures how many insertions, deletions, or substitutions are needed to change one string into another.

Dynamic programming efficiently computes edit distance by building a table of solutions to smaller subproblems.

Optimizing space and customizing operation costs make edit distance practical for large and real-world problems.

Understanding edit distance connects to many fields, from spell checking to genetics, showing its broad importance.

Common mistakes include incorrect initialization and ignoring the symmetry of the standard 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