Question

Find the edit distance between HORSE and NORTH Please give a dynamic-programming table for computing this distance

Answer 1

Edit distance:

Edit distance is the minimum number of edit operations required to convert from string 1 to string 2

Code:

def editDist(str1, str2):
    m=len(str1)
    n=len(str2)
    # this table will stores the results
    dp = [[0 for x in range(n + 1)] for x in range(m + 1)] 
  
    for i in range(m + 1): 
        for j in range(n + 1):      #filling the table with bottom up approach
            if i == 0:           # i==0 then insert the dp[0][j] as j
                dp[i][j] = j    # minimum operations = j
            elif j == 0: # j==0 then insert the dp[i][0] as i
                dp[i][j] = i    # minimum operations = i 
            elif str1[i-1] == str2[j-1]:   #if characters are equal then ignore last 
                dp[i][j] = dp[i-1][j-1] 
            else:                    #else consider the possibilities
                dp[i][j] = 1 + min(dp[i][j-1],dp[i-1][j],dp[i-1][j-1])       
                                    #Insert    #Remove    # Replace 
    return dp 
  
# Driver program 
str1 = "HORSE"
str2 = "NORTH"
m=len(str1)
n=len(str2)
dp=editDist(str1, str2) 
for i in range(m+1):
    for j in range(n+1):
        print(dp[i][j],"", end="")
    print()

print("Minimum edit Distance between ",str1," and ",str2," is :", dp[-1][-1])

SCREENSHOT FOR INDENTATION REFERENCE :

Output :

******

I HOPE YOU UNDERSTAND THIS PROGRAM , FOR ANY CLARIFICATION COMMENT, I AM HAPPY TO HELP YOU . PLEASE GIVE ME FEEDBACK AS WELL

PLEASE UPVOTE : )

*******