import numpy as np
def edit_distance(s1, s2):
    m = len(s1)
    n = len(s2)

    dp = np.zeros((m+1,n+1))

    for i in range(m + 1):
        dp[i][0] = i   # delete all characters

    for j in range(n + 1):
        dp[0][j] = j   # insert all characters

    for i in range(1, m + 1):
        for j in range(1, n + 1):

            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]   # no operation needed
            else:
                dp[i][j] = 1 + min(
                    dp[i - 1][j],      # delete
                    dp[i][j - 1],      # insert
                    dp[i - 1][j - 1]   # substitute
                )

    return dp[m][n]


sstring=input("Enter the source string")
tstring_list=input("Enter the traget strings separated by space")
tstring_list=tstring_list.split()
min_dist=9999
for tstring in tstring_list:
    dist=edit_distance(sstring,tstring)
    print("Edit distance between ", sstring, " and ", tstring, " is ", str(dist))
    if (dist < min_dist):
        min_dist=dist
        min_string=tstring
print("Target string with minimum edit distance is ",min_string)
