Bird
0
0

Given the strings "cat" and "cut", what will be the Levenshtein distance computed by this Python code snippet?

medium📝 Predict Output Q5 of 15
NLP - Text Similarity and Search
Given the strings "cat" and "cut", what will be the Levenshtein distance computed by this Python code snippet?
def lev_dist(s, t):
    dp = [[0]*(len(t)+1) for _ in range(len(s)+1)]
    for i in range(len(s)+1):
        dp[i][0] = i
    for j in range(len(t)+1):
        dp[0][j] = j
    for i in range(1, len(s)+1):
        for j in range(1, len(t)+1):
            cost = 0 if s[i-1] == t[j-1] else 1
            dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + cost)
    return dp[-1][-1]

lev_dist("cat", "cut")
A2
B0
C1
D3
Step-by-Step Solution
Solution:
  1. Step 1: Compare characters of "cat" and "cut"

    Only the middle character differs: 'a' vs 'u'.
  2. Step 2: Calculate minimum edits

    One substitution is needed, so Levenshtein distance is 1.
  3. Final Answer:

    1 -> Option C
  4. Quick Check:

    One substitution difference [OK]
Quick Trick: One character difference means distance 1 [OK]
Common Mistakes:
MISTAKES
  • Counting zero edits
  • Counting insertions instead
  • Misreading characters

Want More Practice?

15+ quiz questions · All difficulty levels · Free

Free Signup - Practice All Questions
More NLP Quizzes