def edit_distance(s1, s2, i, j, dp):
    if i == 0:
        return j
    if j == 0:
        return i

    if dp[i][j] != -1:
        return dp[i][j]

    if s1[i-1] == s2[j-1]:
        dp[i][j] = edit_distance(s1, s2, i-1, j-1, dp)
    else:
        dp[i][j] = 1 + min(
            edit_distance(s1, s2, i, j-1, dp),   # insert
            edit_distance(s1, s2, i-1, j, dp),   # delete
            edit_distance(s1, s2, i-1, j-1, dp)  # replace
        )

    return dp[i][j]


s1 = input("Enter first string: ")
s2 = input("Enter second string: ")

dp = [[-1 for _ in range(len(s2)+1)] for _ in range(len(s1)+1)]	

print("Edit Distance:", edit_distance(s1, s2, len(s1), len(s2), dp))