Edit Distance Problem Levenshtein in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Levenshtein Distance Calculation

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

DSA Go

package main
import "fmt"
func min(a, b, c int) int {
 if a < b {
  if a < c {
   return a
  }
  return c
 }
 if b < c {
  return b
 }
 return c
}
func levenshtein(a, b string) int {
 la := len(a)
 lb := len(b)
 dp := make([][]int, la+1)
 for i := range dp {
  dp[i] = make([]int, lb+1)
 }
 for i := 0; i <= la; i++ {
  dp[i][0] = i
 }
 for j := 0; j <= lb; j++ {
  dp[0][j] = j
 }
 for i := 1; i <= la; i++ {
  for j := 1; j <= lb; j++ {
   if a[i-1] == b[j-1] {
    dp[i][j] = dp[i-1][j-1]
   } else {
    dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1]+1)
   }
  }
 }
 return dp[la][lb]
}
func main() {
 fmt.Println(levenshtein("kitten", "sitting"))
}

A 2

B 4

C 3

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'->'s', substitute 'e'->'i', and 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, Deletion, Substitution

B Insertion, Deletion, Transposition

C Substitution, Transposition, Reversal

D Insertion, Reversal, Deletion

💡 Hint

Levenshtein distance counts the minimum edits needed using basic operations.

Levenshtein distance counts insertions, deletions, and substitutions only. Transpositions are not counted in Levenshtein but in other metrics like Damerau-Levenshtein.

🔧 Debug

advanced

Identify the Error in Levenshtein Implementation

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

DSA Go

package main
import "fmt"
func levenshtein(a, b string) int {
 la := len(a)
 lb := len(b)
 dp := make([][]int, la)
 for i := range dp {
  dp[i] = make([]int, lb)
 }
 for i := 0; i < la; i++ {
  dp[i][0] = i
 }
 for j := 0; j < lb; j++ {
  dp[0][j] = j
 }
 for i := 1; i < la; i++ {
  for j := 1; j < lb; j++ {
   if a[i-1] == b[j-1] {
    dp[i][j] = dp[i-1][j-1]
   } else {
    dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1]+1)
   }
  }
 }
 return dp[la-1][lb-1]
}
func min(a, b, c int) int {
 if a < b {
  if a < c {
   return a
  }
  return c
 }
 if b < c {
  return b
 }
 return c
}
func main() {
 fmt.Println(levenshtein("abc", "yabd"))
}

A output: 3

B runtime error: index out of range

C output: 2

D compilation error: missing return statement

💡 Hint

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

The dp array is created with size la and lb, but loops and indexing use la and lb as if arrays had length la+1 and lb+1, causing index out of range error.

🚀 Application

advanced

Minimum Edit Distance for Spell Checker

You want to find the closest word to 'speling' from the list ['spelling', 'spieling', 'selling', 'spring'] using Levenshtein distance. Which word will have the minimum distance?

A spelling

B spieling

C selling

D spring

💡 Hint

Calculate the number of edits needed to convert 'speling' to each word.

The word 'spelling' differs by one insertion ('l') from 'speling', which is fewer edits than the others.

🧠 Conceptual

expert

Time Complexity of Levenshtein Distance Algorithm

What is the time complexity of the classic dynamic programming algorithm for computing the Levenshtein distance between two strings of lengths m and n?

A O(m^2 + n^2)

B O(m + n)

C O(max(m, n))

D O(m * n)

💡 Hint

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

The algorithm fills a 2D table of size m+1 by n+1, so it runs in O(m * n) time.

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