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")