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):
s1 = input()
s2 = input()
x = [[0 for i in range(len(s2))]for j in range(len(s1))]

def g(i,j):
    if i == 0 or j == 0:
        if s1[i] == s2[j]:
            x[i][j] = abs(i-j)
        else:
            if i == 0:
                x[i][j] = x[i][j-1] + 1
            else:
                x[i][j] = x[i-1][j] + 1
    elif s1[i] == s2[j]:
        x[i][j] = min(x[i-1][j-1],x[i][j-1]+1,x[i-1][j]+1)
    else:
        x[i][j] = min(x[i-1][j-1]+1,x[i][j-1]+1,x[i-1][j]+1)
        

for i in range(len(s1)):
    for j in range(len(s2)):
        g(i,j)

print(x[len(s1)-1][len(s2)-1])

Solution (Python):
s1 = input()
n1 = len(s1)
s2 = input()
n2 = len(s2)

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

if s1[0] == s2[0]: D[0][0] = 0
else: D[0][0] = 1
for j in range(1, n2):
    if s1[0] == s2[j]:
        delta = abs(j)
        D[0][j] = delta
    else:
        D[0][j] = D[0][j-1]+1
for i in range(1, n1):
    if s1[i] == s2[0]:
        delta = abs(i)
        D[i][0] = delta
    else:
        D[i][0] = D[i-1][0]+1
        
for i in range(1, n1):
    for j in range(1, n2):
        if s1[i] == s2[j]:
            D[i][j] = min(D[i-1][j-1], D[i-1][j]+1, D[i][j-1]+1)
        else:
            D[i][j] = min(D[i-1][j-1]+1, D[i-1][j]+1, D[i][j-1]+1)
            

print(D[n1-1][n2-1])

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

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

Solution (Python):



def ed(l1,l2):
    dp=[[0 for x in range(len(l2)+1)] for y in range(len(l1)+1)]
    
    for i in range(1,len(l1)+1):
        dp[i][0]=i
    for i in range(1,len(l2)+1):
        dp[0][i]=i


    for i in range(1,len(l1)+1):
        for j in range(1,len(l2)+1):
            if l1[i-1]==l2[j-1]:
                cost=0
            else:
                cost=1
            dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+cost)
 
    return dp[len(l1)][len(l2)]


l1=list(input())
l2=list(input())
print(ed(l1,l2))

Solution (Python):
def ed(str1,str2):
    f=[[0 for i in range(len(str2)+1)]for j in range(len(str1)+1)]
    for i in range(len(str1)+1):
        f[i][0]=i;
    for i in range(len(str2)+1):
        f[0][i]=i;
    for i in range(1,len(str1)+1):
        for j in range(1,len(str2)+1):
           if str1[i-1]==str2[j-1]:
              f[i][j]=f[i-1][j-1]
           else:
              f[i][j]=min(f[i-1][j-1]+1,f[i-1][j]+1,f[i][j-1]+1)
    return f[-1][-1]

x=input()
y=input()
print(ed(x,y))

Solution (Python):
def LD(str1,str2):
    A = [j for j in range(+len(str2)+1)]
    for i in range(len(str1)):
        A_copy = A[:]
        A[0] = i+1
        for j in range(len(str2)):
            if(str1[i]==str2[j]):
                cost = 0
            else:
                cost = 1
            A[j+1] = min(A[j]+1,A[j+1]+1,A_copy[j]+cost)
    print(A[-1])

str1 = input()
str2 = input()
LD(str1,str2)

Solution (Python):
def ED(X,Y):
    p=len(X)
    q=len(Y)
    Z=[[0 for i in range(q+1)]for j in range(p+1)]
    for i in range(1,p+1):
        Z[i][0]=Z[i-1][0]+1
    for i in range(1,q+1):
        Z[0][i]=Z[0][i-1]+1
    for i in range(p):
        for j in range(q):
            if X[i]==Y[j]:
              Z[i+1][j+1]=min(Z[i][j],Z[i+1][j]+1,Z[i][j+1]+1)
            else:
                Z[i+1][j+1]=min(Z[i][j]+1,Z[i+1][j]+1,Z[i][j+1]+1)
    return Z[i+1][j+1]
X=input()
Y=input()
c=ED(X,Y)
print(c)

Solution (Python):
def levenshtein(X,Y):
    f=[[0 for i in range(len(Y)+1)]for j in range(len(X)+1)]
    for i in range(len(X)+1):
        f[i][0]=i
    for j in range(len(Y)+1):
        f[0][j]=j
    for i in range(1,len(X)+1):
        for j in range(1,len(Y)+1):
            if X[i-1]==Y[j-1]:
                f[i][j]=min(f[i-1][j]+1,f[i][j-1]+1,f[i-1][j-1])
            else:
                f[i][j]=min(f[i-1][j]+1,f[i][j-1]+1,f[i-1][j-1]+1)
    return f[len(X)][len(Y)]

X=input()
Y=input()

print(levenshtein(X,Y))

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)

    
str1 = input()
str2 = input()
leven = Levenshtein(str1,str2)
print(leven.dist)

Solution (Python):
x = input(); n_x = len(x);
y = input(); n_y = len(y);
s = [[i+j for j in range(n_y+1)] for i in range(n_x+1)]
for i in range(n_x):
    for j in range(n_y):
        s[i+1][j+1] = min(s[i+1][j]+1,s[i][j+1]+1,s[i][j]+1*(x[i]!=y[j]))   
print(s[n_x][n_y])

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

Solution (Python):
def search(X,Y):

 n=len(X)
 m=len(Y)
 p=[i for i in range(m+1)]
 for i in range(n):
  q=list(range(m+1))
  q[0] = i+1
  for j in range(m):
   if X[i]==Y[j]:
    cost=0
   else:
    cost=1
   q[j+1]=min(p[j+1]+1,q[j]+1,p[j]+cost)
  p,q=q,p
 
 return p[m]


X=input()
Y=input()

print(search(X,Y))

Solution (Python):
X=input()
Y=input()
dp=[[0 for j  in range(len(X) + 1)]for k in range(len(Y)+1)]

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

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

print(dp[len(Y)][len(X)])

Solution (Python):
s1=list(input())
s2=list(input())
s1.insert(0,0)
s2.insert(0,0)
l=[[0 for i in range(len(s2))] for j in range(len(s1))]
for i in range(len(s1)):
	for j in range(len(s2)):
		if j==0:
			l[i][j]=i
		elif i==0:
			l[i][j]=j
		else:
			if s1[i]==s2[j]:
				c=0
			else:
				c=1
			l[i][j]=min(l[i-1][j]+1,l[i][j-1]+1,l[i-1][j-1]+c)
print(l[len(s1)-1][len(s2)-1])

Solution (Python):
def search(a,b):
    na=len(a)
    nb=len(b)
    array = [[0]*(nb+1) for _ in range(na+1)]
    for i in range(na+1):
        array[i][0]=i
    for j in range(nb+1):
        array[0][j]=j
    for i,x in enumerate(a,1):
        prerow=array[i-1]
        row=array[i]
        for j,y in enumerate(b,1):
            if x == y:
                row[j]=prerow[j-1]
            else:
                row[j]=min(prerow[j], prerow[j-1], row[j-1])+1
    
    return array[-1][-1]

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

Solution (Python):

def search(a,b):
    na=len(a)
    nb=len(b)
    array = [[0]*(nb+1) for _ in range(na+1)]
    for i in range(na+1):
        array[i][0]=i
    for j in range(nb+1):
        array[0][j]=j
    for i,x in enumerate(a,1):
        prerow=array[i-1]
        row=array[i]
        for j,y in enumerate(b,1):
            if x == y:
                row[j]=prerow[j-1]
            else:
                row[j]=min(prerow[j], prerow[j-1], row[j-1])+1
    return array[-1][-1]
a=input()
b=input()
print(search(a,b))

Solution (Python):
def levenshtein(str1, str2):
    if len(str1) == 0 or len(str2) == 0: return max(len(str1), len(str2))
    
    dp = [[None for i in range(len(str2)+1)] for i in range(len(str1)+1)]
    for i in range(len(str1)+1): dp[i][0] = i
    for j in range(len(str2)+1): dp[0][j] = j

    for i in range(1, len(str1)+1):
        for j in range(1, len(str2)+1):
            val = dp[i-1][j-1] if str1[i-1] == str2[j-1] else dp[i-1][j-1]+1
            dp[i][j] = min(val, dp[i-1][j]+1, dp[i][j-1]+1)
    return dp[-1][-1]

s1 = input()
s2 = input()

print(levenshtein(s1, s2))

Solution (Python):
a = list(input())
b = list(input())

if len(a) == 0 or len(b) == 0:
	print(max(len(a),len(b)))

else:
	dp = [[None for i in range(len(b)+1)] for j in range(len(a)+1)]
	for i in range(len(a)+1):
		dp[i][0] = i
	for i in range(len(b)+1):
		dp[0][i] = i

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

print(dp[-1][-1])

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

memo = [[0 for i in range(len(s_2)+1)] for j in range(len(s_1) + 1)]
flag = [[False for i in range(len(s_2)+1)] for j in range(len(s_1) + 1)]

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

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

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

Solution (Python):
import sys
fin = sys.stdin.readline

s1 = fin()[:-1]
s2 = fin()[:-1]
len_s1 = len(s1)
len_s2 = len(s2)

def c_replace(x, y, i, j):
    if x[i] == y[j]:
        return 0
    else:
        return 1



dp = [[0] * (len(s2) + 1) for _ in range(len_s1 + 1)]


for i in range(len_s1):
    dp[i][len_s2] = len_s1 - i
for j in range(len_s2):
    dp[len_s1][j] = len_s2 - j

for i in reversed(range(len(s1))):
    for j in reversed(range(len(s2))):
        dp[i][j] = min(dp[i][j+1] + 1, dp[i+1][j] + 1, dp[i+1][j+1] + c_replace(s1, s2, i, j))

print(dp[0][0])

Solution (Python):
X=input()
Y=input()
dp=[[0 for y in range(1+len(Y))] for x in range(1+len(X))]
for x in range(len(X)):
    dp[x+1][0]=x+1
    for y in range(len(Y)):
        dp[0][y+1]=y+1
        if X[x]==Y[y]:cost=0
        elif X[x]!=Y[y]:cost=1
        dp[1+x][1+y]=min(dp[1+x][y]+1,dp[x][1+y]+1,dp[x][y]+cost)
print(dp[len(X)][len(Y)])

Solution (Python):
def levenshtein_distance(a, b):
    m = len(a)
    n = len(b)
    ld = [[m + n for j in range(n + 1)] for i in range(m + 1)]
    for i in range(m + 1):
        ld[i][0] = i
    for j in range(n + 1):
        ld[0][j] = j
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            ld[i][j] = min(ld[i-1][j]+1,
                           ld[i][j-1]+1,
                           ld[i-1][j-1]+(a[i-1] != b[j-1]))
    return ld[m][n]


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

Solution (Python):

"""
Combinatorial - Edit Distance (Levenshtein Distance)
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_E&lang=jp

"""
import sys


def solve(word1, word2):
    n, m = len(word1), len(word2)
    dp = [[0] * (m + 1) for _ 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 word1[i - 1] == word2[j - 1] else 1
            dp[i][j] = min(dp[i - 1][j] + 1,         
                           dp[i][j - 1] + 1,         
                           dp[i - 1][j - 1] + cost)  
    return dp[n][m]


def main(args):
    s1 = input()
    s2 = input()
    ans = solve(s1, s2)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def leven(s1, s2):
    n1 = len(s1)
    n2 = len(s2)
    dp = [[0]*(n1+1) for _ in range(n2+1)]

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

    for j in range(1, n2+1):
        for k in range(1, n1+1):
            m = min(dp[j-1][k], dp[j][k-1])+1
            if s1[k-1] == s2[j-1]:  
                m = min(m, dp[j-1][k-1])
            else:
                m = min(m, dp[j-1][k-1]+1)
            dp[j][k] = m
    print(dp[-1][-1])


s1 = input()[:-1]
s2 = input()[:-1]
leven(s1, s2)

Solution (Python):
import sys

def ed(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0 for j in range(n + 1)] for i 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(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]
            else:
                dp[i][j] = min(dp[i - 1][j - 1], dp[i -1][j], dp[i][j - 1]) + 1
    return dp[m][n]
    
    
if __name__ == '__main__':
    s1 = sys.stdin.readline()
    s2 = sys.stdin.readline()
    
    sys.stdout.write(str(ed(s1, s2)))
    sys.stdout.write('\n')

Solution (Python):

def levenshtein_distance(str1, str2):
    d = [[0] * (len(str2) + 1) for _ in range(len(str1) + 1)]

    for i1 in range(len(str1) + 1):
       d[i1][0] = i1
    for i2 in range(len(str2) + 1):
       d[0][i2] = i2

    for i1 in range(len(str1)):
        for i2 in range(len(str2)):
            cost = 0 if str1[i1] == str2[i2] else 1
            d[i1 + 1][i2 + 1] = min(d[i1    ][i2 + 1] + 1,     
                                    d[i1 + 1][i2    ] + 1,     
                                    d[i1    ][i2    ] + cost)  


    return d[-1][-1]

from sys import stdin
readline = stdin.readline

s1, s2 = [readline().strip() for _ in range(2)]
print(levenshtein_distance(s1, s2))

Solution (Python):
s1 = input()
s2 = input()
def delta(s1, s2):
    pv = list(range(len(s2)+1))
    for i, c1 in enumerate(s1):
        cv = [i+1]
        for j, c2 in enumerate(s2):
            cv.append(min(pv[j+1]+1, cv[j]+1, pv[j]+(c1 != c2)))
        pv = cv
    return pv[-1]

print(delta(s1, s2))

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

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

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

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

Solution (Python):
s1 = raw_input(); l1 = len(s1)
s2 = raw_input(); l2 = len(s2)
dp = [[10**6]*(l2+1) for i in xrange(l1+1)]
dp[0][0] = 0
for i in xrange(l1+1):
    for j in xrange(l2+1):
        if i < l1:
            dp[i+1][j] = min(dp[i][j]+1, dp[i+1][j])
        if j < l2:
            dp[i][j+1] = min(dp[i][j]+1, dp[i][j+1])
        if i < l1 and j < l2:
            dp[i+1][j+1] = min(dp[i][j] + (s1[i]!=s2[j]), dp[i+1][j+1])
print dp[l1][l2]

Solution (Python):
def levenshtein(str1, str2):
    l1, l2 = len(str1), len(str2)
    dp = [list(range(l2 + 1))] + [[i + 1] + [0] * l2 for i in range(l1)]

    for i1, c1 in enumerate(str1):
        for i2, c2 in enumerate(str2):
            dp[i1 + 1][i2 + 1] = min(dp[i1][i2 + 1] + 1, dp[i1 + 1][i2] + 1, dp[i1][i2] + int(c1 != c2))

    return dp[l1][l2]


print(levenshtein(input(), input()))

Solution (Python):
def levenshtein(str1, str2):
    prev_dp = list(range(len(str2) + 1))

    for i1, c1 in enumerate(str1):
        current_dp = [i1 + 1]
        for i2, c2 in enumerate(str2):
            current_dp.append(min(prev_dp[i2 + 1] + 1, current_dp[i2] + 1, prev_dp[i2] + int(c1 != c2)))
        prev_dp = current_dp

    return prev_dp[-1]


print(levenshtein(input(), input()))

Solution (Python):
def levenshtein(str1, str2):
    prev_dp = list(range(len(str2) + 1))

    for i1, c1 in enumerate(str1):
        current_dp = [i1 + 1]
        current_dp.extend(min(prev_dp[i2 + 1] + 1, current_dp[i2] + 1, prev_dp[i2] + int(c1 != c2))
                          for i2, c2 in enumerate(str2))
        prev_dp = current_dp

    return prev_dp[-1]


print(levenshtein(input(), input()))

Solution (Python):
s1 = input()
s2 = input()
strlen = [n for n in range(len(s1)+1)]
for i,char1 in enumerate(s2):
    inner = [i+1]
    for k,char2 in enumerate(s1):
        inner.append(min(strlen[k+1]+1,inner[k]+1,strlen[k]+(char1!=char2)))
    strlen = inner
print(strlen[len(s1)])

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

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

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

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

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

Solution (Python):



"""
input:
acac
acm

output:
2
"""

import sys


def solve():
    dp = [[0] * (len_w2 + 1) for _ in range(len_w1 + 1)]

    for i in range(len_w1 + 1):
        for j in range(len_w2 + 1):
            if not i:
                dp[i][j] = j
            elif not j:
                dp[i][j] = i

            elif w1[i - 1] == w2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]

            else:
                dp[i][j] = min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) + 1

    return dp[-1][-1]


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    w1, w2 = _input
    len_w1, len_w2 = len(w1), len(w2)
    print(solve())

Solution (Python):



"""
input:
acac
acm

output:
2
"""

import sys


def solve():
    dp = [[0] * (len_w2 + 1) for _ in range(len_w1 + 1)]

    for i in range(len_w1 + 1):
        for j in range(len_w2 + 1):
            if not i:
                dp[i][j] = j
            elif not j:
                dp[i][j] = i

            elif w1[i - 1] == w2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]

            else:
                dp[i][j] = min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) + 1

    return dp[-1][-1]


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    w1, w2 = _input
    len_w1, len_w2 = len(w1), len(w2)
    print(solve())

Solution (Python):



"""
input:
acac
acm

output:
2
"""

import sys


def solve():
    dp = [[0] * (len_w2 + 1) for _ in range(len_w1 + 1)]

    for i in range(len_w1 + 1):
        for j in range(len_w2 + 1):
            if not i:
                dp[i][j] = j
            elif not j:
                dp[i][j] = i

            elif w1[i - 1] == w2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]

            else:
                dp[i][j] = min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) + 1

    return dp[-1][-1]


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    w1, w2 = _input
    len_w1, len_w2 = len(w1), len(w2)
    print(solve())

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

m = len(s1)
n = len(s2)
dp = [[0 for j in xrange(n + 1)] for i in xrange(m + 1)]

for i in xrange(m + 1):
    dp[i][0] = i

for j in xrange(1, n + 1):
    dp[0][j] = j

for i in xrange(1, m + 1):
    for j in xrange(1, n + 1):
        f = 0 if s1[i - 1] == s2[j - 1] else 1
        dp[i][j] = min(
            dp[i - 1][j - 1] + f,
            dp[i - 1][j] + 1,
            dp[i][j - 1] + 1
        )

print dp[m][n]

Solution (Python):
s1=raw_input()
s2=raw_input()
m=len(s1);n=len(s2)
dp=[[float("inf")]*(n+1) for _ in xrange(m+1)]
for i in xrange(m+1):
    dp[i][0]=i
for j in xrange(n+1):
    dp[0][j]=j
delete=1
insert=1
replacement=1
for i in xrange(m):
    for j in xrange(n):
        if s1[i]!=s2[j]:
            dp[i+1][j+1]=min(dp[i][j+1]+delete,dp[i+1][j]+insert,dp[i][j]+replacement)
        else:
            dp[i+1][j+1]=min(dp[i][j+1]+delete,dp[i+1][j]+insert,dp[i][j]+0)
print dp[m][n]

Solution (Python):

def ED():
    X = " " + input()
    Y = " " + input()
    ed = [[float("inf")]*(len(X)) for _ in range(len(Y))]
    
    for j in range(len(X)):
        ed[0][j] = j
    for i in range(len(Y)):
        ed[i][0] = i
        
    for j in range(1, len(X)):
        for i in range(1, len(Y)):
            if (X[j] == Y[i]):
                ed[i][j] = ed[i-1][j-1]
            else:
                ed[i][j] = min(ed[i-1][j-1], ed[i][j-1], ed[i-1][j]) + 1
            
    return ed[len(Y)-1][len(X)-1]

if __name__ == '__main__':
     print(ED())

Solution (Python):
import sys

s1 = sys.stdin.readline().strip()
s2 = sys.stdin.readline().strip()

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

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

print memo[-1][-1]

Solution (Python):
s1 = input()
s2 = input()
s1len = len(s1);s2len = len(s2)
dp = [[0 for i in range(s2len+1)] for i in range(s1len+1)]
dic = [0]*3
for i in range(s1len+1):
    for j in range(s2len+1):
        if i == 0:
            dp[i][j] = j
        elif j == 0:
            dp[i][j] = i
        else:
            dic[0] = dp[i][j] = dp[i-1][j-1] if s1[i-1] == s2[j-1] else dp[i-1][j-1]+1
            dic[1] = dp[i-1][j]+1
            dic[2] = dp[i][j-1]+1
            dp[i][j] = min(dic)

print(dp[s1len][s2len])

Solution (Python):

def levenshtein(s1, s2):
    prev = range(len(s1) + 1)
    for i, c2 in enumerate(s2, start=1):
        cur = [i] + [0] * len(s1)
        for j, tpl in enumerate(zip(s1, prev[1:], cur, prev), start=1):
            c1, p1, p2, p3 = tpl
            cur[j] = min(p1 + 1, p2 + 1, p3 + (c2 != c1))
        prev = cur
    return cur[len(s1)]


s1 = input()
s2 = input()

ans = levenshtein(s1, s2)

print(ans)

Solution (Python):
s1 = input()
s2 = input()
s1_len = len(s1)
s2_len = len(s2)
dp = [[i if j == 0 else j if i == 0 else None for j in range(s2_len+1)] for i in range(s1_len+1)]

for i in range(1, s1_len+1):
    for j in range(1, s2_len+1):
        n1 = dp[i-1][j-1] if s1[i-1] == s2[j-1] else dp[i-1][j-1]+1
        n2 = dp[i-1][j]+1
        n3 = dp[i][j-1]+1
        dp[i][j] = min(n1, n2, n3)

print(dp[s1_len][s2_len])

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


def levenshtein(s1, s2):
    s1_len = len(s1)
    prev = range(s1_len+1)
    current = None

    for i, c1 in enumerate(s2, start=1):
        current = [i] * (s1_len+1)
        for j, c2 in enumerate(s1, start=1):
            n1 = prev[j-1] if c1 == c2 else prev[j-1]+1
            n2 = prev[j]+1
            n3 = current[j-1]+1
            current[j] = min(n1, n2, n3)
        prev = current

    return current[-1]

print(levenshtein(s1, s2))

Solution (Python):
def levenshtein(s1, s2):
    n, m = len(s1), len(s2)
    dp = [[0] * (m+1) for _ 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)
            
    return dp[n][m]

s1 = input()
s2 = input()

print(levenshtein(s1, s2))

Solution (Python):
def levenshtein(s1, s2):
    n, m = len(s1), len(s2)
    dp = [[0] * (m+1) for _ 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)
            
    return dp[n][m]

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

    print(levenshtein(s1, s2))
    
if __name__ == '__main__':
    solve()

Solution (Python):
a = input()
b = input()
la = len(a)
lb = len(b)
L = [[0 for j  in range(la + 1)] for k in range(lb + 1)]
for i in range(la + 1):
    L[0][i] = i
for i in range(lb + 1):
    L[i][0] = i
for  m in range(1, la + 1):
    for n in range(1, lb + 1):
        if a[m-1] == b[n-1]:
            L[n][m] = L[n-1][m-1]
        else:
            L[n][m] = min(L[n-1][m], L[n][m-1], L[n-1][m-1]) + 1
print(L[-1][-1])

Solution (Python):
s1=raw_input()
s2=raw_input()
d=[0]*(len(s1)+1)
for i in range(len(s1)+1):
    if i==0:
        d[i]=range(len(s2)+1)
    else:
        d[i]=[i]+[0]*len(s2)

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

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

Solution (Python):
def edit_dist(s,t):
    n = len(s)
    m = len(t)
    pre = [i for i in range(m+1)]
    for i in range(n):
        nxt = list(range(m+1))
        nxt[0] = i+1
        for j in range(m):
            cost = 0 if s[i] == t[j] else 1
            nxt[j+1] = min(pre[j+1] + 1, nxt[j] + 1, pre[j] + cost)
            
        pre, nxt = nxt, pre
    return pre[m]

s = input()
t = input()

print(edit_dist(s,t))

Solution (Python):
def ans(n, m):
    ln = len(n)
    lm = len(m)
    dp = [[0] * (lm+1) for _ in range(ln+1)]
    
    for i in range(ln+1):
        dp[i][0] = i
    for j in range(lm+1):
        dp[0][j] = j
    for i in range(1,ln+1):
        for j in range(1,lm+1):
            if n[i-1] == m[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = min(dp[i][j-1]+1, dp[i-1][j]+1, dp[i-1][j-1]+1)
    return dp[-1][-1]
n = input()
m = input()
print(ans(n, m))

Solution (Python):
n = input()
m = input()
ln = len(n)
lm = len(m)
dp = [[0] * (lm+1) for _ in range(ln+1)]
for i in range(ln+1):
    dp[i][0] = i
for j in range(lm+1):
    dp[0][j] = j
for i in range(1,ln+1):
    for j in range(1,lm+1):
        if n[i-1] == m[j-1]:
            dp[i][j] = dp[i-1][j-1]
        else:
            dp[i][j] = min(dp[i][j-1]+1, dp[i-1][j]+1, dp[i-1][j-1]+1)
print(dp[-1][-1])

Solution (Python):
def levenshtein(str1, str2):
    if len(str1) == 0 or len(str2) == 0: return max(len(str1), len(str2))
    
    dp = [[None for i in range(len(str2)+1)] for i in range(len(str1)+1)]
    for i in range(len(str1)+1): dp[i][0] = i
    for j in range(len(str2)+1): dp[0][j] = j

    for i in range(1, len(str1)+1):
        for j in range(1, len(str2)+1):
            val = dp[i-1][j-1] if str1[i-1] == str2[j-1] else dp[i-1][j-1]+1
            dp[i][j] = min(val, dp[i-1][j]+1, dp[i][j-1]+1)
    return dp[-1][-1]

s1 = input()
s2 = input()

print(levenshtein(s1, s2))

Solution (Python):
s=input()
t=input()
n=len(s)
m=len(t)
INF=10**18
dp=[[INF]*(m+1) for _ in range(n+1)]
dp[0][0]=0
for i in range(-1,n):
  for j in range(-1,m):
    if i==-1 and j==-1:continue
    if i>=0 and j>=0:
      if s[i]==t[j]:dp[i+1][j+1]=min(dp[i][j],dp[i+1][j+1])
      else:dp[i+1][j+1]=min(dp[i][j]+1,dp[i+1][j+1])
    if i>=0:dp[i+1][j+1]=min(dp[i][j+1]+1,dp[i+1][j+1])
    if j>=0:dp[i+1][j+1]=min(dp[i+1][j]+1,dp[i+1][j+1])
print(dp[n][m])

Solution (Python):
s = list(input())
n = len(s)
t = list(input())
m = len(t)
dp = [[0] * (m+1) for _ 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(n):
    for j in range(m):
        cost = 0 if s[i] == t[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[n][m])

Solution (Python):
def main():
    import sys

    readline = sys.stdin.readline

    s1 = readline().rstrip()
    s2 = readline().rstrip()

    ls1 = len(s1)
    ls2 = len(s2)

    
    
    inf = 10 ** 3
    dp = [[inf] * (ls2 + 1) for _ in [0] * (ls1 + 1)]
    for i in range(ls1 + 1):
        dp[i][0] = i
    for j in range(ls2 + 1):
        dp[0][j] = j

    for i in range(ls1):
        for j in range(ls2):
            res = 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] + res)
    print(dp[ls1][ls2])


main()

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

dp = [[0] * (len(s2)+1) for _ 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(1, len(s1)+1):
    for j in range(1, len(s2)+1):
        dp[i][j] = min(
                dp[i-1][j-1] + (0 if s1[i-1] == s2[j-1] else 1),
                dp[i-1][j] + 1,
                dp[i][j-1] + 1
        )





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

Solution (Python):
import sys

import math
import collections

import bisect
import itertools
import fractions

import copy

import decimal

import queue



sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7


ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))





def main():
    s1 = list(input())
    s2 = list(input())

    s1_l = len(s1)
    s2_l = len(s2)

    dp = [[0 for _ in range(s1_l + 1)] for _ in range(s2_l + 1)]
    for i in range(s1_l + 1):
        dp[0][i] = i
    for i in range(s2_l + 1):
        dp[i][0] = i

    for i in range(1, s2_l+1):
        for j in range(1, s1_l+1):
            cost = 0 if s1[j-1] == s2[i-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[s2_l][s1_l])


if __name__ == '__main__':
    main()

Solution (Python):
x = list(input())
y = list(input())

lx = len(x)
ly = len(y)
INF = 10**10
dp = [[INF]*(lx+1) for i in range(ly+1)]
dp[0][0] = 0

for i in range(ly+1): dp[i][0] = i
for i in range(lx+1): dp[0][i] = i

for i in range(ly):
    for j in range(lx):
        if y[i] == x[j]:
            dp[i+1][j+1] = min(dp[i+1][j]+1,dp[i][j+1]+1,dp[i][j])
        else:
            dp[i+1][j+1] = min(dp[i+1][j]+1,dp[i][j+1]+1,dp[i][j]+1)

print(dp[ly][lx])