Question

How do i create a python function that will calculate the Levenshtein distance given a user input of two words? I am aware that there are packages already made to do this, but I want to create my own. Please explain all the steps.

https://en.wikipedia.org/wiki/Levenshtein_distance#:~:text=Informally%2C%20the%20Levenshtein%20distance%20between,considered%20this%20distance%20in%201965.

Answer 1

Hey here is answer to your question.

In case of any doubt comment below. Please UPVOTE if you Liked the answer.

def solve(s, t):
    if s == "":
        return len(t)
    if t == "":
        return len(s)
    if s[-1] == t[-1]:
        cost = 0
    else:
        cost = 1
       
    res = min([solve(s[:-1], t)+1,
               solve(s, t[:-1])+1, 
               solve(s[:-1], t[:-1]) + cost])

    return res

print(solve("abcd", "cdefgh"))

a nad b are words given to function.

The Levenshtein distance between two strings a and b is given by lev_a,b(len(a), len(b)) where lev_a,b(i, j) is equal to

• max(i, j) if min(i, j)=0
• otherwise:

  min(leva,b(i-1, j) + 1,
      leva,b(i, j-1) + 1,
      leva,b(i-1, j-1) + 1ai≠bj)
  

where 1_ai≠bj is the indicator function equal to 0 when ai=bj and equal to 1 otherwise, and leva,b(i, j) is the distance between the first i characters of a and the first j characters of b.</sub>

The Levenshtein distance has the following properties:

• It is zero if and only if the strings are equal.
• It is at least the difference of the sizes of the two strings.
• It is at most the length of the longer string.
• Triangle inequality: The Levenshtein distance between two strings is no greater than the sum of their Levenshtein distances from a third string.