Problem:
Edit Distance (Levenshtein Distance) Find the edit distance between given two words s1 and s2 . The disntace is the minimum number of single-character edits required to change one word into the other. The edits including the following operations:  insertion : Insert a character at a particular position.  deletion : Delete a character at a particular position.  substitution : Change the character at a particular position to a different character  Input  s1  s2  Two words s1 and s2 are given in the first line and the second line respectively. The words will consist of lower case characters. Output Print the edit distance in a line. Constraints  1 ≤ length of s1 ≤ 1000  1 ≤ length of s2 ≤ 1000  Sample Input 1 acac
acm Sample Output 1 2 Sample Input 2 icpc
icpc Sample Output 2 0

Solution (Python):
def edit_dist(S0, S1):
    i = len(S0)
    j = len(S1)
    dp = [i for i in range(len(S1) + 1)]

    for i in range(1, i+1):
        dp_prev = dp[:]
        dp[0] = i
        for j in range(1, j+1):
            dp[j] = min(dp_prev[j-1] + (S0[i-1] is not S1[j-1]), dp_prev[j] + 1, dp[j-1] + 1)
    return dp[-1]

if __name__ == "__main__":
    s0 = input()
    s1 = input()
    print(edit_dist(s0, s1))

Solution (Python):
S = list(input())
T = list(input())
dp = [[float('inf')]*(len(T)+1) for _ in range(len(S)+1)]
dp[0][0] = 0

for i in range(len(S)):
  dp[i+1][0] = i+1
for j in range(len(T)):
  dp[0][j+1] = j+1
for i in range(len(S)):
  a = S[i]
  for j in range(len(T)):
    b = T[j]
    dp[i+1][j+1] = min(dp[i+1][j]+1, dp[i][j+1]+1, dp[i][j]+(a != b))

print(dp[len(S)][len(T)])

Solution (Python):
def ld(s1, s2):
    l1 = len(s1)
    l2 = len(s2)
    if l1 == 0 and l2 == 0:
        return 0
    if l1 == 0:
        return l2
    if l2 == 0:
        return l1

    INF = 10**10
    DP = [[INF]*(l2+1) for _ in range(l1+1)] 
    for p1 in range(l1+1):
        DP[p1][0] = p1 
    for p2 in range(l2+1):
        DP[0][p2] = p2 

    for p1 in range(1,l1+1):
        for p2 in range(1,l2+1):
            if s1[p1-1] == s2[p2-1]:
                DP[p1][p2] = min(DP[p1][p2],DP[p1-1][p2-1])
            else:
                DP[p1][p2] = min(DP[p1][p2],DP[p1-1][p2]+1)
                DP[p1][p2] = min(DP[p1][p2],DP[p1][p2-1]+1)
                DP[p1][p2] = min(DP[p1][p2],DP[p1-1][p2-1]+1)
    return DP[l1][l2]

S1 = input() 
S2 = input() 
print(ld(S1,S2))

Solution (Python):
def main():
    s = input()
    t = input()
    n, m = len(s), len(t)
    dp = [[j if i == 0 else 10 ** 10 for i in range(m + 1)] for j in range(n + 1)]
    dp[0] = [i for i in range(m + 1)]
    for i in range(n):
        for j in range(m):
            dp[i + 1][j + 1] = min(dp[i][j + 1] + 1,
                                   dp[i + 1][j] + 1,
                                   dp[i][j] + 1 - (s[i] == t[j]))
    ans = dp[n][m]
    print(ans)


main()

Solution (Python):
import sys
input = sys.stdin.readline
INF = float("inf")


def main():
    s1 = input()[:-1]
    s2 = input()[:-1]
    S1 = len(s1)
    S2 = len(s2)

    dp = [[INF]*(S2 + 1) for _ in range(S1 + 1)]
    for i in range(S1 + 1):
        dp[i][0] = i
    for j in range(S2 + 1):
        dp[0][j] = j
    
    for i in range(S1):
        for j in range(S2):
            if s1[i:i+1]==s2[j:j+1]:
                dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j])
            else:
                dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j] + 1)
            dp[i+1][j+1] = min(dp[i+1][j+1], dp[i+1][j] + 1)
            dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j+1] + 1)
    
    
    
    print(dp[S1][S2])


if __name__ == '__main__':
    main()

Solution (Python):
INF = 10 ** 10

s1,s2 = input(),input()
n,m = len(s1),len(s2)
dp = [[INF] * (m + 1) for i in range(n + 1)]
dp[0][0] = 0
for i in range(n + 1):
	for j in range(m + 1):
		if i >= 1:
			dp[i][j] = min(dp[i][j],dp[i - 1][j] + 1)
		if j >= 1:
			dp[i][j] = min(dp[i][j],dp[i][j - 1] + 1)
		if i >= 1 and j >= 1:
			dp[i][j] = min(dp[i][j],dp[i - 1][j - 1] + (s1[i - 1] != s2[j - 1]))
print(dp[n][m])

Solution (Python):
s1 = input()
s2 = input()
dict = dict([])
s1_num = []
s2_num = []
for s in s1:
    if not s in dict:
        dict[s] = len(dict)
    s1_num.append(dict[s])
for s in s2:
    if not s in dict:
        dict[s] = len(dict)
    s2_num.append(dict[s])

s1_len = len(s1_num)
s2_len = len(s2_num)

lst = [[0] * (s2_len + 1) for _ in range(s1_len + 1)]
lst[0] = [i for i in range(s2_len + 1)]
for x in range(s1_len + 1):
    lst[x][0] = x

for i in range(1, s1_len + 1):
    for j in range(1, s2_len + 1):
        if s1_num[i - 1] == s2_num[j - 1]:
            lst[i][j] = min((lst[i - 1][j - 1]), (lst[i - 1][j] + 1), (lst[i][j - 1] + 1))
        else:
            lst[i][j] = min((lst[i - 1][j - 1] + 1), (lst[i - 1][j] + 1), (lst[i][j - 1] + 1))
print(lst[s1_len][s2_len])

Solution (Python):
s1=input()
s2=input()
mp=[[0]*(len(s1)+1) for _ in range(len(s2)+1)]

for n in range(1,len(s2)+1):
    mp[n][0]+=mp[n-1][0]+1
for m in range(1,len(s1)+1):
    mp[0][m]+=mp[0][m-1]+1

for i in range(1,len(s2)+1):
    for j in range(1,len(s1)+1):
        mp[i][j]=min(mp[i-1][j]+1,
                    mp[i][j-1]+1,
                    mp[i-1][j-1]+(s1[j-1]!=s2[i-1]))
print(mp[-1][-1])

Solution (Python):
s1 = input()
s2 = input()
l1 = len(s1)
l2 = len(s2)
mat = [[l1 + l2 for _ in range(l1 + 1)] for _ in range(l2 + 1)]

for i in range(l1+1):
    mat[0][i] = i
for j in range(l2+1):
    mat[j][0] = j

for j in range(l2):
    for i in range(l1):
        m = mat[j][i] + 1 if s1[i] != s2[j] else mat[j][i]
        mat[j+1][i+1] = min(m, mat[j][i+1] + 1, mat[j+1][i] + 1)
print(mat[l2][l1])

Solution (Python):
s1=input()
s2=input()
l1,l2=len(s1),len(s2)
dp=[[0]*(l2+1) for _ in range(l1+1)] 
for i in range(l1+1):
    dp[i][0]=i
for j in range(l2+1):
    dp[0][j]=j
for i in range(1,l1+1):
    for j in range(1,l2+1):
        dp[i][j]=min(dp[i][j-1]+1,dp[i-1][j]+1,dp[i-1][j-1]+(s1[i-1]!=s2[j-1]))
print(dp[l1][l2])

Solution (Python):


s1 = input()
s2 = input()

memo = [[i for i in range(len(s1) + 1)] if j == 0 else [j if i == 0 else -1 for i in range(len(s1) + 1)] for j in range(len(s2) + 1)]
for i in range(1, len(s2) + 1):
    for j in range(1, len(s1) + 1):
        
        cng = memo[i - 1][j - 1] if s1[j - 1] == s2[i - 1] else memo[i - 1][j - 1] + 1
        
        memo[i][j] = min(cng, memo[i][j - 1] + 1, memo[i - 1][j] + 1)

print(memo[len(s2)][len(s1)])

Solution (Python):
s1 = input()
s2 = input()

dp = [[0 for j in range(len(s2)+1)] for k in range(len(s1)+1)]

for i in range(len(s1)+1):
    dp[i][0] = i

for i in range(len(s2)+1):
    dp[0][i] = i

for i in range(0, len(s1)):
    for j in range(0, len(s2)):
        cost = 0 if s1[i] == s2[j] else 1
        dp[i+1][j+1] = min(dp[i][j+1]+1, dp[i+1][j]+1, dp[i][j]+cost)

print(dp[len(s1)][len(s2)])

Solution (Python):
def edit_dist(s, t):
    INF = float('inf')
    th = INF
    m, n = len(s), len(t)
    if abs(m - n) >= th:
        return INF
    dp = [[INF] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1): dp[i][0] = i
    for j in range(n + 1): dp[0][j] = j
    for i in range(m):
        for j in range(n):
            dp[i + 1][j + 1] = min(dp[i][j] + (s[i] != t[j]), dp[i][j + 1] + 1, dp[i + 1][j] + 1)
    return dp[m][n]

print(edit_dist(input(), input()))

Solution (Python):
class Levenshtein:

    def initArray(self,str1,str2):
        distance = []
        for i in range(len(str1)+1):
            distance.append([0]*(len(str2)+1))
            distance[i][0] = i
        for j in range(len(str2)+1):
            distance[0][j] = j
        return distance

    def editDist(self,str1,str2,distance):
        dist = [0]*3
        for i in range(1,len(str1)+1):
            for j in range(1,len(str2)+1):
                dist[0] = distance[i-1][j-1] if str1[i-1]==str2[j-1] else distance[i-1][j-1]+1
                dist[1] = distance[i][j-1]+1
                dist[2] = distance[i-1][j]+1
                distance[i][j]=min(dist)
        return distance[i][j]

    def __init__(self,str1,str2):
        self.str1 = str1
        self.str2 = str2
        Levenshtein.distance = self.initArray(str1,str2)
        Levenshtein.dist = self.editDist(str1,str2,Levenshtein.distance)

if __name__ == '__main__':
    str1 = input()
    str2 = input()
    leven = Levenshtein(str1,str2)
    print(leven.dist)

Solution (Python):
def Levenshtein(s:str, t:str) -> int:
	ls, lt = len(s), len(t)
	dp = [[0]*(lt+1) for _ in range(ls+1)]
	dp[0] = list(range(lt+1))
	for i in range(ls+1):
		dp[i][0] = i
	for i,a in enumerate(s):
		for j,b in enumerate(t):
			if a==b:
				dp[i+1][j+1] = dp[i][j]
			else:
				dp[i+1][j+1] = min(dp[i][j], dp[i+1][j], dp[i][j+1]) + 1
	return dp[ls][lt]
	
def solve():
	print(Levenshtein(input(),input()))
	
if __name__=="__main__":
	solve()

Solution (Python):
def main():
    s=input()
    t=input()
    n=len(s)
    m=len(t)
    memo=[[n+m for _ in [0]*(m+1)] for _ in [0]*(n+1)]
    memo[0][0]=0
    
    for i in range(n+m):
        for j in range(i+1):
            k=i-j
            if 0<=j<n and 0<=k<m:
                if s[j]==t[k]:
                    memo[j+1][k+1]=min(memo[j+1][k+1],memo[j][k])
                else:
                    memo[j+1][k]=min(memo[j+1][k],memo[j][k]+1)
                    memo[j][k+1]=min(memo[j][k+1],memo[j][k]+1)
                    memo[j+1][k+1]=min(memo[j+1][k+1],memo[j][k]+1)
            elif j==n:
                memo[j][k+1]=min(memo[j][k+1],memo[j][k]+1)
            elif k==m:
                memo[j+1][k]=min(memo[j+1][k],memo[j][k]+1)
    print(memo[n][m])
                
if __name__ == '__main__':
    main()

Solution (Python):
s_1 = input()
s_2 = input()

dp = [[0 for _ in range(len(s_2)+1)] for _ in range(len(s_1)+1)]

for i in range(len(s_2)+1):
	dp[0][i] = i
for i in range(len(s_1)+1):
	dp[i][0] = i

for i in range(1,len(s_1)+1):
	for j in range(1,len(s_2)+1):
		if s_1[i-1] == s_2[j-1]:
			dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1])
		else:
			dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1]+1)

print(dp[len(s_1)][len(s_2)])

Solution (Python):
import sys


def levenshtein_dist(s1: str, s2: str) -> int:
    m = len(s1)
    n = len(s2)
    table = [[sys.maxsize for j in range(n + 1)] for i in range(m + 1)]
    for i in range(m + 1):
        table[i][0] = i
    for j in range(n + 1):
        table[0][j] = j
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            table[i][j] = min(table[i - 1][j] + 1,
                              table[i][j - 1] + 1,
                              table[i - 1][j - 1] + (s1[i - 1] != s2[j - 1]))
    return table[m][n]


if __name__ == "__main__":
    s1: str = input()
    s2: str = input()

    print(f"{levenshtein_dist(s1, s2)}")

Solution (Python):
s = input()
t = input()
w = len(s)+1
h = len(t)+1
dp = []
for i in range(h):
    L = [0]*w
    dp.append(L)
for i in range(w):
    dp[0][i] = i
for i in range(h):
    dp[i][0] = i
for i in range(h-1):
    for j in range(w-1):
        if t[i] == s[j]:
            dp[i+1][j+1] = min(dp[i][j],dp[i][j+1]+1,dp[i+1][j]+1)
        else:
            dp[i+1][j+1] = min(dp[i][j]+1,dp[i][j+1]+1,dp[i+1][j]+1)
print(dp[h-1][w-1])

Solution (Python):
S1 = input()
S2 = input()
arr1 = [i for i in range(len(S1) + 1)]
arr2 = [1 for _ in range(len(S1) + 1)]

for i, s2 in enumerate(S2):
  arr2[0] = arr1[0] + 1
  for j in range(1, len(S1) + 1):
    if s2 == S1[j - 1]:
      cost = 0
    else:
      cost = 1
      
    arr2[j] = min(arr2[j - 1] + 1,
                  arr1[j] + 1,
                  arr1[j - 1] + cost)
  arr1, arr2 = arr2, arr1
  
print(arr1[-1])

Solution (Python):
s1=input()
s2=input()
l1=len(s1)
l2=len(s2)
n=max(l1,l2)

Dp=[[0 for i in range(n+1)] for j in range(n+1)]
for i in range(n+1):
    Dp[0][i] = i
for i in range(n+1):
    Dp[i][0] = i
for j in range(1,n+1):
    for k in range(1,n+1):
        try:
            if s1[j-1]==s2[k-1]:
                cost=0
            else:
                cost=1
            Dp[j][k] = min(Dp[j-1][k]+1, Dp[j][k-1]+1, Dp[j-1][k-1] + cost )
        except:
            pass


print(Dp[l1][l2])

Solution (Python):
s1=input()
s2=input()

def lcs(s,t):
    l1=len(s)
    l2=len(t)
    tb=[[0]*l2 for i in range(l1)]

    for i in range(l1):
        for j in range(l2):
            if s[i]==t[j]:
                if i==0 or j==0:
                    tb[i][j]=abs(j-i)
                    continue
                tb[i][j]=tb[i-1][j-1]
                continue
            if i!=0 and j!=0:
                tb[i][j]=min(tb[i-1][j],tb[i][j-1],tb[i-1][j-1])+1
            elif i==0:
                tb[i][j]=tb[i][j-1]+1
            else:
                tb[i][j]=tb[i-1][j]+1
    print(tb[l1-1][l2-1])

lcs(s1,s2)

Solution (Python):
s1 = " "+input()
s2 = " "+input()
from collections import defaultdict
dp = defaultdict(lambda: defaultdict(lambda: max(len(s1), len(s2))))
dp[0][0] = 0
for i in range(len(s1)-1):
    for j in range(len(s2)-1):
        if s1[i]!=s2[j+1]:
            dp[i][j+1]=min(dp[i][j+1], dp[i][j]+1)

        if s1[i+1]!=s2[j]:
            dp[i+1][j]=min(dp[i+1][j], dp[i][j]+1)

        if s1[i+1]!=s2[j+1]:
            dp[i+1][j+1]=min(dp[i][j]+1, dp[i+1][j]+1, dp[i][j+1]+1)
        else:
            dp[i+1][j+1]=min(dp[i][j], dp[i+1][j]+1, dp[i][j+1]+1)
print(dp[len(s1)-1][len(s2)-1])

Solution (Python):
a = input()
b = input()
dp = [[0 for n in range(len(a) + 1)] for m in range(len(b) + 1)]

for i in range(len(b) + 1):
    for j in range(len(a) + 1):
        if i == 0:
            dp[i][j] = j
        elif j == 0:
            dp[i][j] = i
        else:
            dp[i][j] = min(dp[i - 1][j - 1] + int(a[j - 1] != b[i - 1]), dp[i][j - 1] + 1, dp[i - 1][j] + 1)
print(dp[len(b)][len(a)])

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')

S=input()
N=len(S)
T=input()
M=len(T)


dp = [[INF] * (M+1) for i in range(N+1)]

dp[0][0] = 0
for i in range(N+1):
    for j in range(M+1):
        
        if i < N:
            dp[i+1][j] = min(dp[i+1][j], dp[i][j]+1)
        
        if j < M:
            dp[i][j+1] = min(dp[i][j+1], dp[i][j]+1)
        
        if i < N and j < M:
            dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j]+1)
            if S[i] == T[j]:
                
                dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j])

print(dp[N][M])

Solution (Python):
A = input()
B = input()
a,b = len(A),len(B)
F = [[0 for i in range(b+1)] for i in range(a+1)]
for i in range(a+1):
    for j in range(b+1):
        if i==0:F[i][j] = j
        elif j==0:F[i][j] = i
        else: 
            k = 0 if A[i-1]==B[j-1] else 1
            F[i][j] = min(F[i-1][j]+1,F[i][j-1]+1,F[i-1][j-1]+k)
print(F[a][b])

Solution (Python):
s1 = input()
s2 = input()

n1 = len(s1)
n2 = len(s2)

inf = float('inf')

def cost(j, i):
    return 0 if s1[i] == s2[j] else 1


D = [[inf for i in range(n1 + 1)] for j in range(n2 + 1)]

for i in range(n1 + 1):
    D[0][i] = i
for j in range(n2 + 1):
    D[j][0] = j

for j in range(1, n2 + 1):
    for i in range(1, n1 + 1):
        D[j][i] = min(D[j][i-1] + 1, D[j-1][i] + 1,
                      D[j-1][i-1] + cost(j-1, i-1))

print(D[n2][n1])

Solution (Python):
S=' '+input()
T=' '+input()
n=len(S)
m=len(T)
dp=[[n+m]*(m+1) for _ in range(n+1)]
dp[0][0]=0
for i in range(1,n+1):
    for j in range(1,m+1):
        dp[i][j]=min([dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+(S[i-1]!=T[j-1])])
print(dp[n][m])

Solution (Python):
s1 = input()
s2 = input()

x = len(s1)
y = len(s2)

dp = [[0]*(y+1) for _ in range(x+1)]

for j in range(1,y+1):
    dp[0][j] = dp[0][j-1] + 1

for i in range(1,x+1):
    dp[i][0] = dp[i-1][0] + 1

for i in range(1,x+1):
    for j in range(1,y+1):
            cost = s1[i-1] != s2[j-1]
            dp[i][j] = min(dp[i-1][j-1] + cost, dp[i][j-1] + 1, dp[i-1][j] + 1)

ans = dp[x][y]
print(ans)

Solution (Python):
def levenshtein_distance(s1, s2):
    len_s1 = len(s1)
    len_s2 = len(s2)

    dp = [[0]*(len_s2 + 1) for _ in range(len_s1 + 1)]
    for i in range(len_s1 + 1):
        dp[i][0] = i
    for j in range(len_s2 + 1):
        dp[0][j] = j

    for i in range(len_s1):
        for j in range(len_s2):
            if s1[i] == s2[j]:
                dp[i+1][j + 1] = min(dp[i][j] - 1, dp[i][j + 1], dp[i + 1][j]) + 1
            else:
                dp[i+1][j + 1] = min(dp[i][j], dp[i][j + 1], dp[i + 1][j]) + 1

    return dp[len_s1][len_s2]


s1 = input()
s2 = input()
print(levenshtein_distance(s1, s2))

Solution (Python):
import sys
def main(argv):
    args = sys.argv
    
    
    
    

    s1  = input()
    s2 = input()



    n1 = len(s1)
    n2 = len(s2)
    dp = [[0 for _ in range(n2 + 1)] for _ in range(n1 + 1) ]

    for i in range(0, n1+1):
        dp[i][0] = i
    for j in range(0, n2+1):
        dp[0][j] = j

    for i in range(1, n1+1):
        for j in range(1, n2+1):
            if s1[i-1] == s2[j-1]:
                a = dp[i-1][j-1]
            else:
                a = dp[i-1][j-1]+1
            b = dp[i][j-1] + 1
            c = dp[i-1][j] + 1
            dp[i][j] = min([a,b,c])
            pass
    
    
    print(dp[n1][n2])
if __name__ == '__main__':
    main(sys.argv[1:])

Solution (Python):
s = input()
t = input()
dp = [[0]*(len(s)+1) for i in range(len(t)+1)]
for i in range(len(s)+1):
    dp[0][i] = i
for j in range(len(t)+1):
    dp[j][0] = j
for i in range(len(t)):
    for j in range(len(s)):
        cost = 0
        if t[i]!=s[j]:
            cost+=1
        dp[i+1][j+1] = min(dp[i][j]+cost, dp[i+1][j]+1, dp[i][j+1]+1)
print(dp[-1][-1])

Solution (Python):


a = [None] + list(input())
b = [None] + list(input())
dp = [[float('inf')]*(len(a)) for _ in range(len(b))]
for i in range(len(a)):
    dp[0][i] = i
for i in range(len(b)):
    dp[i][0] = i

for i in range(1,len(b)):
    for j in range(1,len(a)):
        if b[i] == a[j]:
            c = 0
        else:
            c = 1
        dp[i][j] = min(dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+c)

print(dp[len(b)-1][len(a)-1])

Solution (Python):

s1 = input()
s2 = input()
N = len(s1)
M = len(s2)
inf = float("inf")

dp = [ [inf] * (M+1) for _ in range(N+1)]


for m in range(M+1):
    dp[0][m] = m
for n in range(N+1):
    dp[n][0] = n

for n in range(1, N+1):
    for m in range(1, M+1):
        
        cost = 1 - int( s1[n-1] == s2[m-1] )
        dp[n][m] = min( dp[n][m], 
                        dp[n-1][m] + 1,
                        dp[n][m-1] + 1,
                        dp[n-1][m-1] + cost)


print(dp[N][M])

Solution (Python):
s1=input()
s2=input()
dist=[[0 for i in range(len(s1)+1)] for j in range(len(s2)+1)]
for i in range(len(s1)+1):
    dist[0][i]=i
for i in range(len(s2)+1):
    dist[i][0]=i
for i in range(1,len(s2)+1):
    for j in range(1,len(s1)+1):
        k=1
        if s1[j-1]==s2[i-1]:k=0
        dist[i][j]=min(dist[i-1][j]+1,dist[i][j-1]+1,dist[i-1][j-1]+k)
print(dist[len(s2)][len(s1)])

Solution (Python):
def dump(dp, max1, max2):
    return
    for i2 in range(max2 + 1):
        for i1 in range(max1 + 1):
            print('%4d' % dp[i1][i2], end='')
        print()
    print()


inf = 1 << 60
s1 = input()
s2 = input()
max1 = len(s1)
max2 = len(s2)


dp = [[inf] * (max2 + 2) for _ in range(max1 + 2)]

dp[0][0] = 0
dump(dp, max1, max2)

for i2 in range(0,max2+1):
    for i1 in range(0,max1+1):
        if i1 > 0:
            dp[i1][i2] = min(dp[i1][i2], dp[i1-1][i2] + 1)
        if i2 > 0:
            dp[i1][i2] = min(dp[i1][i2], dp[i1][i2-1] + 1)
        if i1 > 0 and i2 > 0:
            if s1[i1-1] == s2[i2-1]:
                dp[i1][i2] = min(dp[i1][i2], dp[i1-1][i2-1])
            else:
                dp[i1][i2] = min(dp[i1][i2], dp[i1-1][i2-1] + 1)
    dump(dp, max1, max2)

print(dp[max1][max2])

Solution (Python):
import sys
sys.setrecursionlimit(10000)

def my_ed(s,t):
    
    mem = {}
    def dp(i,j):
        nonlocal mem,s,t
        if (i,j) in mem.keys():
            return mem[(i,j)]
        if i<0:
            res = j+1
        elif j<0:
            res = i+1
        else:
            res = min(dp(i-1,j)+1,dp(i,j-1)+1,dp(i-1,j-1) + (0 if s[i]==t[j] else 1))
        mem[(i,j)] = res
        
        return res
     
    return dp(len(s)-1,len(t)-1)
 
 
print(my_ed(input(),input()))

Solution (Python):
iipt=lambda:int(input())
miipt=lambda:list(map(int,input().split(" ")))

s=" "+input()
S=len(s)
s+="_"*1123
t=" "+input()
T=len(t)
t+="_"*1123
dp=[[1123]*1123 for i in range(1123)]

dp[0][0]=0
for i in range(S):
    for j in range(T):
        dp[i+1][j]= min(dp[i+1][j], dp[i][j]+1)
        dp[i][j+1]= min(dp[i][j+1], dp[i][j]+1)
        dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j]+(s[i+1]!=t[j+1]))
print(dp[S-1][T-1])

Solution (Python):






def levenshtein_distance(str1, str2):
    l1, l2 = len(str1), len(str2)

    dp = [i for i in range(l2+2)]
    dp[l2+1] = l1 * l2
    dq = dp[:]

    for i, c1 in enumerate(str1):
        dq[0] = i+1
        for j, c2 in enumerate(str2):
            if c1 == c2:
                dq[j+1] = dp[j]
            else:
                dq[j+1] = min(dp[j], dp[j+1], dq[j]) + 1
        dp, dq = dq, dp

    return dp[l2]


def run():
    s1 = input()
    s2 = input()

    print(levenshtein_distance(s1, s2))


if __name__ == '__main__':
    run()

Solution (Python):
s1 = input()
s2 = input()
dp = [[0 for i in range(len(s2)+1)] for j in range(len(s1)+1)]
for i in range(len(s2)+1):
    dp[0][i] = i
for i in range(len(s1)+1):
    dp[i][0] = i
for i in range(1, len(s1)+1):
    for j in range(1, len(s2)+1):
        if s1[i-1] == s2[j-1]:
            dp[i][j] = dp[i-1][j-1]
        else:
            cost = 0 if s1[i-1] == s2[j-1] else 1
            dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1]+cost)
print(dp[-1][-1])

Solution (Python):
def edit_distance(a,b):
    n = len(a)
    m = len(b)
    L = [i for i in range(m+1)] 
    for i in range(1,n+1):
        copy = L[:]     
        L[0] = i   
        for j in range(1,m+1):
            if (a[i-1] == b[j-1]):
                cost = 0
            else:
                cost = 1
            L[j] = min(copy[j] + 1,L[j-1] + 1,copy[j-1] + cost)
            
    return L[-1]
    
    
    
a = input()
b = input()
print(edit_distance(a,b))

Solution (Python):
S = ' ' + input()
T = ' ' + input()

dp = [[i+j for j in range(len(T)+1)] for i in range(len(S)+1)]

for i in range(len(S)):
    for j in range(len(T)):
        c = 0 if S[i] == T[j] else 1
        dp[i+1][j+1] = min(dp[i][j] + c, dp[i][j+1] + 1, dp[i+1][j] + 1)

print(dp[len(S)][len(T)])

Solution (Python):
def ED(a,b):
  x=list(a)
  y=list(b)
  m=len(x)
  n=len(y)
  A=[[0 for i in range(m+1)]for j in range(n+1)]
  for i in range(m+1):
    A[0][i]=i
  for i in range(n+1):
    A[i][0]=i
  
  for i in range(1,n+1):
    for j in range(1,m+1):
      if x[j-1]==y[i-1]:
        cnt=A[i-1][j-1]
      else:
        cnt=A[i-1][j-1]+1
      A[i][j]=min(A[i-1][j]+1,A[i][j-1]+1,cnt)
  return A[n][m]
  

a=input()
b=input()
print(ED(a,b))

Solution (Python):
s1 = input()
s2 = input()


dp = [[float('inf') for i in range(len(s1)+1)] for j in range(len(s2)+1)]

for i in range(len(s1)+1):
    dp[0][i] = i
for j in range(len(s2)+1):
    dp[j][0] = j

for i in range(len(s1)):
    for j in range(len(s2)):
        if s1[i] == s2[j]:
            dp[j+1][i+1] = dp[j][i]
        else:
            dp[j+1][i+1] = min(dp[j][i], dp[j+1][i], dp[j][i+1]) +1
print(dp[len(s2)][len(s1)])

Solution (Python):
s1 = input()
s2 = input()
n = len(s1)
m = len(s2)
dp = [[0 for j in range(m+1)] for i in range(n+1)]
for i in range(n+1):
    dp[i][0] = i
for j in range(m+1):
    dp[0][j] = j
for i in range(1,n+1):
    for j in range(1,m+1):
        cost = 0 if s1[i-1] == s2[j-1] else 1
        dp[i][j] = min(dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+cost)
print(dp[n][m])