Edit Distance Problem Levenshtein in DSA Go - Deep Dive

Overview - Edit Distance Problem Levenshtein

What is it?

The Edit Distance Problem, also known as the Levenshtein distance, measures how many changes are needed to turn one word into another. These changes can be adding, removing, or changing a letter. It helps computers understand how similar two words or strings are. This is useful in spell checking, DNA analysis, and more.

Why it matters

Without this concept, computers would struggle to compare words or texts that are slightly different. For example, spell checkers wouldn't know which word you meant if you typed it wrong. It helps machines understand human errors and variations, making technology smarter and more helpful.

Where it fits

Before learning this, you should understand basic strings and arrays. After this, you can explore more advanced string algorithms like longest common subsequence or dynamic programming optimizations.

Mental Model

Core Idea

Edit distance counts the smallest number of letter changes needed to make two words exactly the same.

Think of it like...

Imagine you have two sentences written on paper, and you want to make them match by erasing, writing, or changing letters one by one. The edit distance is how many such steps you need.

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

Operations:
- Substitute 's' with 'k'
- Substitute 'g' with 'n'
- Insert 'g'

Minimum 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 anywhere - Delete a letter - Substitute one letter for another Each operation counts as one step.

Result

You can transform any word into any other word by a sequence of these steps.

Knowing these three operations is key because all edit distance calculations are based on counting these steps.

2

Foundation

What Is Edit Distance Exactly?

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

For example, to change 'cat' to 'cut': - Substitute 'a' with 'u' (1 step) So, edit distance = 1. To change 'cat' to 'cats': - Insert 's' at the end (1 step) Edit distance = 1.

Result

Edit distance gives a number representing how different two words are.

Understanding that edit distance is a count of minimal changes helps you see it as a measure of similarity.

3

Intermediate

Dynamic Programming Approach

🤔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: - If letters match, take diagonal value - Else, take 1 + minimum of left (insert), top (delete), diagonal (substitute) This builds up the answer step by step.

Result

The bottom-right cell of the table gives the full edit distance between the two words.

Using dynamic programming turns an exponential problem into a fast, manageable one by remembering past answers.

4

Intermediate

Implementing Levenshtein Distance in Go

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

Concept: Translate the dynamic programming logic into Go code using slices (arrays).

We create a 2D slice of size (len(word1)+1) x (len(word2)+1). Initialize first row and column with incremental values (cost of inserting or deleting all letters). Fill the rest using the rules: - If letters equal, cost = previous diagonal - Else, cost = 1 + min(insert, delete, substitute) Return the value at bottom-right.

Result

The function returns the minimum edit distance as an integer.

Knowing how to implement the algorithm in code solidifies understanding and prepares for practical use.

5

Intermediate

Tracing the Algorithm 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 table with 7 rows and 8 columns. Fill first row and column with 0 to length values. Compare letters and fill cells: - Substitute 'k' with 's' (cost 1) - Match 'i' (cost 0) - Match 't' (cost 0) - Match 't' (cost 0) - Substitute 'e' with 'i' (cost 1) - Match 'n' (cost 0) - Insert 'g' (cost 1) Final edit distance = 3

Result

The table shows the minimum edits needed is 3.

Tracing helps you see how the algorithm builds the solution from small parts.

6

Advanced

Optimizing Space Usage

🤔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 the current and previous row of the table.

Since each cell depends only on the left, top, and diagonal cells, we can keep just two rows: - Previous row for top values - Current row being computed This reduces space from O(m*n) to O(min(m,n)) where m and n are word lengths.

Result

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

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

7

Expert

Handling Unicode and Real-World Text

🤔Before reading on: do you think treating strings as bytes is enough for all languages? Commit to your answer.

Concept: Consider multi-byte characters and normalization in real text processing.

In Go, strings are byte sequences but characters can be multiple bytes (UTF-8). We must convert strings to runes (Unicode code points) to handle all languages correctly. Also, text normalization (like accents) affects edit distance. Ignoring these can cause wrong results in international applications.

Result

Proper handling ensures accurate edit distance for all languages and scripts.

Knowing this prevents bugs and inaccuracies in global software dealing with text.

Under the Hood

The algorithm builds a matrix where each cell represents the minimum edits to convert prefixes of the two strings. It uses previous results to avoid recalculating subproblems, a technique called dynamic programming. Internally, it compares characters and chooses the cheapest operation (insert, delete, substitute) to reach the solution.

Why designed this way?

The problem is exponential if solved by trying all sequences of edits. Dynamic programming was chosen to break it into smaller overlapping problems, saving time by reusing results. Alternatives like recursive brute force were too slow, and other algorithms like Damerau-Levenshtein add complexity for specific cases.

┌─────────────┬─────┬─────┬─────┬─────┐
│             │  '' │  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  │
└─────────────┴─────┴─────┴─────┴─────┘

Myth Busters - 4 Common Misconceptions

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

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

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

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

Quick: Is the edit distance always the difference in word lengths? Commit yes or no.

Common Belief: Edit distance equals the difference in lengths of the two words.

Reality: Edit distance depends on letter differences, not just length; words can have same length but large edit distance.

Why it matters: Assuming this causes underestimating how different two words really are.

Quick: Does treating strings as bytes always work for edit distance? Commit yes or no.

Common Belief: You can calculate edit distance by comparing raw bytes of strings.

Reality: For multi-byte characters (like emojis or accented letters), you must compare Unicode characters (runes) to get correct results.

Why it matters: Ignoring this causes wrong distances in languages other than plain ASCII English.

Quick: Is the dynamic programming table always needed in full? Commit yes or no.

Common Belief: You must keep the entire dynamic programming table in memory to compute edit distance.

Reality: Only two rows are needed at a time, reducing memory usage significantly.

Why it matters: Not knowing this wastes memory and limits scalability.

Expert Zone

1

The choice of cost for insert, delete, and substitute can be adjusted for specific applications, affecting results.

2

Levenshtein distance does not handle transpositions (swapping letters) efficiently; other algorithms like Damerau-Levenshtein do.

3

Normalization of Unicode strings before computing distance is crucial to avoid counting visually identical but differently encoded characters as different.

When NOT to use

Avoid Levenshtein distance when transpositions are common errors; use Damerau-Levenshtein instead. For very long strings or real-time needs, consider approximate or heuristic methods like BK-trees or Trie-based searches.

Production Patterns

Used in spell checkers to suggest corrections, in DNA sequence analysis to measure mutations, and in search engines to find close matches. Often combined with indexing structures to speed up queries.

Connections

Dynamic Programming

Levenshtein distance is a classic example of dynamic programming applied to string problems.

Understanding this algorithm deepens comprehension of dynamic programming principles like overlapping subproblems and optimal substructure.

Bioinformatics Sequence Alignment

Edit distance is foundational to sequence alignment algorithms comparing DNA or proteins.

Knowing edit distance helps grasp how biological sequences are compared and mutations measured.

Human Language Processing

Edit distance models how humans perceive similarity between words, aiding in speech recognition and text correction.

This connection shows how computer algorithms mimic human error correction and understanding.

Common Pitfalls

#1 Treating strings as byte arrays instead of Unicode characters.

Wrong approach:

func Levenshtein(a, b string) int {
// compares bytes directly
for i := 0; i < len(a); i++ {
if a[i] != b[i] { /* ... */ }
}
return 0
}

Correct approach:

func Levenshtein(a, b string) int {
runesA := []rune(a)
runesB := []rune(b)
// compare runes for correct Unicode handling
for i := 0; i < len(runesA); i++ {
if runesA[i] != runesB[i] { /* ... */ }
}
return 0
}

Root cause:

Misunderstanding that Go strings are UTF-8 encoded and characters can be multiple bytes.

#2 Initializing dynamic programming table incorrectly causing wrong results.

Wrong approach:

for i := 0; i <= lenA; i++ {
dp[i][0] = 0 // should be i
}
for j := 0; j <= lenB; j++ {
dp[0][j] = 0 // should be j
}

Correct approach:

for i := 0; i <= lenA; i++ {
dp[i][0] = i
}
for j := 0; j <= lenB; j++ {
dp[0][j] = j
}

Root cause:

Not recognizing that converting empty string to prefix requires insertions or deletions equal to prefix length.

#3 Assuming edit distance only counts substitutions.

Wrong approach:

if a[i] != b[j] {
dp[i][j] = dp[i-1][j-1] + 1 // only substitution
} else {
dp[i][j] = dp[i-1][j-1]
}

Correct approach:

dp[i][j] = min(
dp[i-1][j] + 1, // deletion
dp[i][j-1] + 1, // insertion
dp[i-1][j-1] + cost // substitution
)

Root cause:

Oversimplifying the problem and ignoring insertions and deletions.

Key Takeaways

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

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

Optimizing space by storing only two rows of the table is possible because each step depends only on nearby values.

Handling Unicode properly is essential for accurate edit distance in real-world text processing.

Levenshtein distance is foundational in many fields, from spell checking to bioinformatics, but has limits when transpositions matter.

Practice

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

easy

A. The number of matching characters in the same positions

B. The number of characters in the longer string

C. The minimum number of single-character edits to change one string into the other

D. The length difference between the two strings

Solution

1. Step 1: Understand the definition of Edit Distance

   Edit Distance counts how many changes (insert, delete, replace) are needed to convert one string to another.

2. Step 2: Identify what is measured

   It measures the minimum number of single-character edits required.

3. Final Answer:

   The minimum number of single-character edits to change one string into the other -> Option C

4. Quick Check:

   Edit Distance = minimum edits [OK]

Hint: Edit Distance counts minimal edits to match strings [OK]

Common Mistakes:

• Confusing edit distance with string length
• Thinking it counts only matching characters
• Assuming it measures length difference only

2. Which of the following Go function signatures correctly represents a function to compute Levenshtein distance between two strings s1 and s2?

easy

A. func Levenshtein(s1, s2 string) string

B. func Levenshtein(s1, s2 string) int

C. func Levenshtein(s1 int, s2 int) string

D. func Levenshtein(s1, s2 int) int

Solution

1. Step 1: Identify input types for strings

   The function must accept two strings as input parameters.

2. Step 2: Identify output type

   The output is an integer representing the edit distance.

3. Final Answer:

   func Levenshtein(s1, s2 string) int -> Option B

4. Quick Check:

   Input: strings, Output: int [OK]

Hint: Function inputs are strings, output is int distance [OK]

Common Mistakes:

• Using int instead of string for inputs
• Returning string instead of int
• Mixing input types incorrectly

3. What is the output of the following Go code snippet computing Levenshtein distance between "kitten" and "sitting"?

package main
import "fmt"
func main() {
    s1 := "kitten"
    s2 := "sitting"
    dist := Levenshtein(s1, s2)
    fmt.Println(dist)
}

func Levenshtein(a, b string) int {
    m, n := len(a), len(b)
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
    }
    for i := 0; i <= m; i++ {
        dp[i][0] = i
    }
    for j := 0; j <= n; j++ {
        dp[0][j] = j
    }
    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            cost := 0
            if a[i-1] != b[j-1] {
                cost = 1
            }
            dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1]+cost)
        }
    }
    return dp[m][n]
}

func min(x, y, z int) int {
    if x < y {
        if x < z {
            return x
        }
        return z
    }
    if y < z {
        return y
    }
    return z
}

medium

A. 6

B. 4

C. 5

D. 3

Solution

1. Step 1: Understand the strings and operations

   "kitten" to "sitting" requires substitutions k->s, e->i, plus insert g.

2. Step 2: Calculate minimum edits

   Minimum edits are 2 substitutions + 1 insertion = 3 edits total.

3. Final Answer:

   3 -> Option D

4. Quick Check:

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

Hint: Count substitutions and insertions carefully [OK]

Common Mistakes:

• Counting only substitutions
• Ignoring insertions
• Miscounting character positions

4. Identify the bug in this Go function computing Levenshtein distance:

func Levenshtein(a, b string) int {
    m, n := len(a), len(b)
    dp := make([][]int, m)
    for i := range dp {
        dp[i] = make([]int, n)
    }
    for i := 0; i < m; i++ {
        dp[i][0] = i
    }
    for j := 0; j < n; j++ {
        dp[0][j] = j
    }
    for i := 1; i < m; i++ {
        for j := 1; j < n; j++ {
            cost := 0
            if a[i-1] != b[j-1] {
                cost = 1
            }
            dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1]+cost)
        }
    }
    return dp[m-1][n-1]
}

medium

A. dp slice sizes should be m+1 and n+1, not m and n

B. The cost calculation should be outside the loops

C. The min function is missing

D. The return statement should be dp[0][0]

Solution

1. Step 1: Check dp slice initialization

   dp must have size m+1 by n+1 to include empty string cases, but code uses m and n only.

2. Step 2: Understand impact of wrong sizes

   Using m and n causes index out of range errors and incorrect base cases.

3. Final Answer:

   dp slice sizes should be m+1 and n+1, not m and n -> Option A

4. Quick Check:

   dp size = m+1, n+1 [OK]

Hint: dp array must cover empty prefixes with +1 size [OK]

Common Mistakes:

• Initializing dp with wrong sizes
• Misplacing cost calculation
• Returning wrong dp cell

5. Given two strings s1 = "intention" and s2 = "execution", what is the minimum edit distance using Levenshtein algorithm? Consider insertions, deletions, and substitutions only.

hard

A. 6

B. 5

C. 8

D. 7

Solution

1. Step 1: Analyze differences between "intention" and "execution"

   Compare characters and count edits: substitutions and insertions/deletions as needed.

2. Step 2: Calculate minimal edits

   Minimum edits calculated are 6 total.

3. Final Answer:

   6 -> Option A

4. Quick Check:

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

Hint: Count substitutions plus insertions/deletions carefully [OK]

Common Mistakes:

• Underestimating substitutions
• Ignoring insertions/deletions
• Confusing character positions