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):
s = input()
t = input()
ls, lt = len(s), len(t)


dp = [[0 for _ in range(lt + 1)] for j in range(ls + 1)]
for i in range(ls + 1):
    dp[i][0] = i
for j in range(lt + 1):
    dp[0][j] = j

for i in range(ls):
    for j in range(lt):
        if s[i] == t[j]:
            cost = 0
        else:
            cost = 1
        dp[i + 1][j + 1] = min(dp[i][j+1] + 1, dp[i+1][j] + 1, dp[i][j] + cost)
print(dp[ls][lt])

Solution (Python):
def main():
    S = input()
    T = input()
    ns = len(S)
    nt = len(T)

    dp = [[0]*(nt+1) for _ in [0]*(ns+1)]
    for i in range(ns+1):
        dp[i][0] = i
    for j in range(nt+1):
        dp[0][j] = j
    
    di_1 = dp[0]
    for s, di in zip(S, dp[1:]):
        j = 0
        di_1j_1 = di_1[0]
        dij_1 = di[0]
        for t in T:
            j += 1
            if s == t:
                dmin = di_1j_1
                di_1j = di_1[j]
            else:
                dmin = di_1j = di_1[j]
                if dij_1 < dmin:
                    dmin = dij_1
                if di_1j_1 < dmin:
                    dmin = di_1j_1
                dmin += 1
            di[j] = dij_1 = dmin
            di_1j_1 = di_1j
        di_1 = di
    
    print(dp[-1][-1])

if __name__ == '__main__':
    main()

Solution (Python):
s1 = input()
s2 = input()
l1 = len(s1)
l2 = len(s2)
INF = l1 + l2


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


ans = [[INF] * (1 + l1) for _ in range(1 + l2)]

ans[0][0] = 0



for i in range(l2 + 1):
    for j in range(l1 + 1):
        if i == 0:
            ans[i][j] = j
        elif j == 0:
            ans[i][j] = i
        else:
            ans[i][j] = min(
                ans[i - 1][j] + 1, ans[i][j - 1] + 1, match(i, j) + ans[i - 1][j - 1]
            )
print(ans[l2][l1])

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


def main():
    S = readline().rstrip()
    T = readline().rstrip()

    N, M = len(S), len(T)
    dp = [[0] * (M+1) for _ in range((N+1))]
    dp[0] = [i for i in range(M+1)]
    for i in range(N+1):
        dp[i][0] = i
    
    for i, s in enumerate(S):
        for j, t in enumerate(T):
            if s == t:
                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

    print(dp[N][M])


if __name__ == '__main__':
    main()

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

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**10
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    s1 = SS()
    s2 = SS()

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

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

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

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

if __name__ == '__main__':
    resolve()

Solution (Python):
s = input().strip()
t = input().strip()

dist = [[0]*(len(t)+1) for _ in range(len(s)+1)]
for i in range(1, len(s)+1):
    dist[i][0] = i

for i in range(1, len(t)+1):
    dist[0][i] = i

for i in range(1, len(s)+1):
    for j in range(1, len(t)+1):
        if s[i-1] == t[j-1]:
            dist[i][j] = dist[i-1][j-1]
        else:
            dist[i][j] = min(dist[i-1][j-1], dist[i][j-1], dist[i-1][j]) + 1

print(dist[len(s)][len(t)])

Solution (Python):
def solve(a,b):
    dp=[[0]*(len(b)+1) for _ in range(len(a)+1)]
    for i in range(len(a)+1):
        dp[i][0]=i
    for j in range(len(b)+1):
        dp[0][j]=j
    for i in range(1,len(a)+1):
        for j in range(1,len(b)+1):
            if a[i-1]==b[j-1]:
                dp[i][j]=min(dp[i-1][j-1],dp[i-1][j]+1,dp[i][j-1]+1)
            else:
                dp[i][j]=min(dp[i-1][j-1]+1,dp[i-1][j]+1,dp[i][j-1]+1)
    return dp[len(a)][len(b)]

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

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


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

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

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

Solution (Python):
S1 = input()
S2 = input()
R = len(S1)
C = len(S2)
dp = [[0]*(C+1) for i in range(R+1)]
for i in range(R+1):
    dp[i][0] = i
for j in range(C+1):
    dp[0][j] = j

for i in range(1,R+1):
    for j in range(1,C+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][j-1]+1,dp[i-1][j-1]+1)

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

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7

s1 = input()
s2 = input()

len_1 = len(s1)
len_2 = len(s2)

dp = [[INF]*(len_2+1) for _ in range(len_1+1)]
dp[0][0] = 0

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

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



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




print(dp[len_1][len_2])

Solution (Python):
s1 = input()
s2 = input()
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):
    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

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

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

def Levenshtein_d(X,Y):
    XL = len(X)
    YL = len(Y)
    dp = [[0 for j in range(YL+1)] for i in range(XL+1)]
    for i in range(1,XL+1):
        dp[i][0] = i
    for j in range(1,YL+1):
        dp[0][j] = j
    for i in range(XL):
        for j in range(YL):
            if X[i] == Y[j]:
                dp[i+1][j+1] = min(dp[i][j+1]+1,dp[i+1][j]+1,dp[i][j])
            else:
                dp[i+1][j+1] = min(dp[i][j+1]+1,dp[i+1][j]+1,dp[i][j]+1)
    return dp[XL][YL]

print(Levenshtein_d(s1,s2))

Solution (Python):
x=input() 
lx=len(x)
y=input()
ly=len(y)
dp=[[0]*(ly+2) for _ in range(lx+2)]
for i in range(0,lx+1):
    dp[i][0]= i
for i in range(0,ly+1):
    dp[0][i]= i
    
for i in range(0,lx):
    for j in range(0,ly):
        if x[i]==y[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][j+1]+1, dp[i+1][j]+1,dp[i][j]+1) 
print(dp[lx][ly])

Solution (Python):
INF = 1 << 31
def main():
    S = input()
    T = input()
    N = len(S)
    M = len(T)
    dp = [[INF] * (M + 1) for _ in range(N + 1)]
    for i in range(N + 1):
        dp[i][0] = i
    for i in range(M + 1):
        dp[0][i] = i
    for i in range(N):
        for j in range(M):
            if S[i] == T[j]:
                dp[i + 1][j + 1] = min(dp[i][j],dp[i + 1][j] + 1,dp[i][j + 1] + 1)
            else:
                dp[i + 1][j + 1] = min(dp[i + 1][j] + 1,dp[i][j + 1] + 1,dp[i][j] + 1)
    print(dp[-1][-1])
if __name__ == '__main__':
    main()

Solution (Python):
def levenshteinDistance(s1: str, s2: str):
    n = len(s1)
    m = len(s2)
    dp = [[0] * (n + 1) for i in range(m + 1)]

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

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

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            substitution_cost = 0
            if s1[j-1] != s2[i-1]:
                substitution_cost = 1
            deletion_cost = dp[i-1][j] + 1
            insertion_cost = dp[i][j-1] + 1
            substitution_cost = dp[i-1][j-1] + substitution_cost
            cost = min(deletion_cost, min(insertion_cost, substitution_cost))
            dp[i][j] = cost
    return dp[m][n]

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

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

def levenshtein_distance(a, b):
    m = [ [0] * (len(b) + 1) for i in range(len(a) + 1) ]

    for i in range(len(a) + 1):
        m[i][0] = i

    for j in range(len(b) + 1):
        m[0][j] = j

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

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

Solution (Python):
def ED(s1,s2):
    m,n = len(s1),len(s2)
    """
    方針：DP
    s1,s2のどちらかが空白文字列ならもう一方の長さ
    s1のi文字目,s2のj文字目まで読み,
    最後が一致していたらその直前までの操作で十分
    一致していなかったら3種の操作のどれかを行う
    """
    dp = [[None for _ in range(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(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],dp[i][j-1],dp[i-1][j-1])+1

    return dp[m][n]

s1 = input()
s2 = input()

ans = ED(s1,s2)
print(ans)

Solution (Python):
A = str(input())
n = len(A)
B = str(input())
m = len(B)

INF = float("inf")
dp = [[INF]*(m+1) for _ in range(n+1)]

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

for i in range(n): 
  for j in range(m):
    if A[i] == B[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[n][m])

Solution (Python):






import sys,bisect
sys.setrecursionlimit(15000)

s1 = sys.stdin.readline().rstrip()
s2 = sys.stdin.readline().rstrip()
l1 = len(s1)
l2 = len(s2)
dp = [[float("inf")]*(l2+1) for _ in range(l1+1)]
dp[0] = list(range(l2+1))

for i in range(l1):
  dp[i][0] = i
  for j in range(l2):
    if s1[i]==s2[j]:
      dp[i+1][j+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[-1][-1])

Solution (Python):
s=list(input())
t=list(input())
l=[0]*(len(s)+1)
for i in range(len(t)+1):
    old=l.copy()
    for j in range(len(s)+1):
        if i==0 or j==0:
            l[j]=max(i,j)
        else:
            c=0 if s[j-1]==t[i-1] else 1
            l[j]=min(l[j-1]+1,old[j]+1,old[j-1]+c)
print(l[len(s)])

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

n = len(s1)
m = len(s2)

DP = [[0]*(m+1) for _ in range(n+1)]

for i in range(n+1):
    DP[i][0] = i

for i in range(m+1):
    DP[0][i] = i

for i in range(1, n+1):
    for j in range(1, m+1):
        c = 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] + c)   

print DP[n][m]

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



DP = [[0 for j in range(len(T)+1)] for i in range(len(S)+1)]
for i in range(len(S)+1):
    DP[i][0] = i
for j in range(len(T)+1):
    DP[0][j] = j
for i in range(1, len(S)+1):
    for j in range(1, len(T)+1):
        if S[i-1] == T[j-1]:
            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(S)][len(T)])

Solution (Python):
def levenshtein_dist(a,b):
    a_size = len(a)
    b_size = len(b)
    inf = float('inf')
    dp = [[a_size+b_size for i in range(a_size+1)] for _ in range(b_size+1)]
    for i in range(b_size+1):
        dp[i][0] = i
    for j in range(a_size+1):
        dp[0][j] = j

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

a = list(input())
b = list(input())
dp = levenshtein_dist(a,b)
print(dp[-1][-1])

Solution (Python):
s=input()
t=input()
n,m=len(s),len(t)
if n==0:
    print(m)
    exit()
if m==0:
    print(n)
    exit()
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

print(pre[m])

Solution (Python):
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7



word = sys.stdin.buffer.readline().decode().rstrip()
input = sys.stdin.buffer.readline().decode().rstrip()

dist = [[INF] * (len(word) + 1) for _ in range(len(input) + 1)]
dist[0] = list(range((len(word) + 1)))
for v in range(1, len(input) + 1):
    vc = input[v - 1]
    dist[v][0] = v
    for w in range(1, len(word) + 1):
        wc = word[w - 1]
        dist[v][w] = min(dist[v][w], dist[v - 1][w - 1] + (0 if vc == wc else 1))
        dist[v][w] = min(dist[v][w], dist[v][w - 1] + 1)
        dist[v][w] = min(dist[v][w], dist[v - 1][w] + 1)
print(dist[-1][-1])

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

def levenshtein_distance(a: str, b: str):
    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):
            if a[i-1] == b[j-1]:
                ld[i][j] = min(ld[i-1][j]+1, ld[i][j-1]+1, ld[i-1][j-1])
            else:
                ld[i][j] = min(ld[i-1][j]+1, ld[i][j-1]+1, ld[i-1][j-1]+1)
    return ld[m][n]

print(levenshtein_distance(s1, s2))

Solution (Python):
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians

from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from functools import reduce
from bisect import bisect_left, insort_left
from heapq import heapify, heappush, heappop

INPUT = lambda: sys.stdin.readline().rstrip()
INT = lambda: int(INPUT())
MAP = lambda: map(int, INPUT().split())
S_MAP = lambda: map(str, INPUT().split())
LIST = lambda: list(map(int, INPUT().split()))
S_LIST = lambda: list(map(str, INPUT().split()))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


class Levenshtein:
    def init_array(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 edit_dist(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.init_array(str1, str2)
        Levenshtein.dist = self.edit_dist(str1, str2, Levenshtein.distance)


def main():
    s1 = INPUT()
    s2 = INPUT()

    leven = Levenshtein(s1, s2)
    print(leven.dist)


if __name__ == '__main__':
    main()

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect_left

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

s1 = input()
s2 = input()

def EditDistance(S, T):
    dp = [[INF]*(len(T)+1) for _ in range(len(S)+1)]
    dp[0][0] = 0
    for i in range(-1, len(S)):
        for j in range(-1, len(T)):
            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+1][j+1], dp[i][j])
                else:
                    dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j] + 1)
            if i >= 0:
                dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j+1] + 1)
            if j >= 0:
                dp[i+1][j+1] = min(dp[i+1][j+1], dp[i+1][j] + 1)
    return dp[len(S)][len(T)]

print(EditDistance(s1, s2))

Solution (Python):
def levenshtein(a,b):
    """
    :param a: string or list
    :param b:  string or list
    :return:  Levenstein distance
    """
    la = len(a)
    lb = len(b)
    dp = [[la+lb]*(lb+1) for i in range(la+1)]
    dp[0][0] = 0
    for i in range(1,la):
        dp[i][0] = i
    for j in range(1,lb):
        dp[0][j] = j
    for i in range(la):
        for j in range(lb):
            dp[i+1][j+1] = min(dp[i][j+1]+1,
                               dp[i+1][j]+1,
                               dp[i][j]+(a[i]!=b[j]))
    l_dist = dp[-1][-1]
    return l_dist

a = input()
b = input()

l_dist = levenshtein(a,b)
print(l_dist)

Solution (Python):
x = input()
y = input()
    
a = len(x)
b = len(y)
dp = [[1000000000]*(b+1) for _ in range(a+1)]
for i in range(a+1):
    dp[i][0] = i
for j in range(b+1):
    dp[0][j] = j

for i in range(a):
    for j in range(b):
        if x[i] == y[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[a][b])

Solution (Python):
def run():
  S1 = list('-'+input())
  len_S1 = len(S1)
  S2 = list('-'+input())
  len_S2 = len(S2)
  dp = [[0] * (len_S2) for _ in range(len_S1)]
  
  for i1 in range(len_S1):
    if S2[0] == S1[i1]: gap = 0
    else: gap = 1
    dp[i1][0] = dp[i1-1][0] + gap
  for i2 in range(len_S2):
    if S1[0] == S2[i2]: gap = 0
    else: gap = 1
    dp[0][i2] = dp[0][i2-1] + gap
  
  for i1 in range(1, len_S1):
    for i2 in range(1, len_S2):
      if S1[i1] == S2[i2]: gap = 0
      else: gap = 1
      dp[i1][i2] = min(dp[i1][i2-1]+1, dp[i1-1][i2]+1,
                       dp[i1-1][i2-1]+gap)
  print(dp[-1][-1])
    
if __name__ == '__main__':
    run()

Solution (Python):
import sys

sys.setrecursionlimit(2003)
s1 = input()
s2 = input()
len1 = len(s1) + 1
len2 = len(s2) + 1
_dp = [[None for _ in range(len2)] for _ in range(len1)]
def dp(i, j):
    if i == 0:
        return j
    if j == 0:
        return i
    if _dp[i][j] == None:
        _dp[i][j] = min(dp(i - 1, j) + 1,         
                        dp(i, j - 1) + 1,         
                        dp(i - 1, j - 1) + (0 if s1[i - 1] == s2[j - 1] else 1))  
    return _dp[i][j]
print(dp(len1 - 1, len2 - 1))

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
from bisect import *
from collections import *
from heapq import *

int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline()[:-1]
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def MF(): return map(float, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LF(): return list(map(float, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
dij = [(0, 1), (1, 0), (0, -1), (-1, 0)]

def main():
    s=SI()
    t=SI()
    n=len(s)
    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,c0 in enumerate(s):
        for j,c1 in enumerate(t):
            dp[i+1][j+1]=min(dp[i][j+1]+1,dp[i+1][j]+1,dp[i][j]+(c0!=c1))
    print(dp[n][m])

main()

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

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


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



print(table[-1][-1])

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

def levenshtein_distance(x, y):
    lx = len(x); ly = len(y)
    dp = [[0 for i in range(ly + 1)] for j in range(lx + 1)]
    
    for i in range(lx + 1):
        dp[i][0] = i
    for j in range(1, ly + 1):
        dp[0][j] = j
        
    for i in range(1, lx + 1):
        for j in range(1, ly + 1):
            if x[i - 1] == y[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[lx][ly]
    
print(levenshtein_distance(x, y))

Solution (Python):


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

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

    for i1 in range(1, n1):
        for i2 in range(1, n2):
            cost = 0 if s1[i1-1] == s2[i2-1] else 1
            dp[i1][i2] = min(
                dp[i1-1][i2]   + 1,
                dp[i1][i2-1]   + 1,
                dp[i1-1][i2-1] + cost)

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

if __name__ == "__main__":
    resolve()

Solution (Python):
S1=input()
S2=input()
dp=[[0 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(1,len(S1)+1):
    for j in range(1,len(S2)+1):
        if S1[i-1]==S2[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(S2)][len(S1)])

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):
x = input()
y = input()
co = [[0] * (len(x)+1) for i in range(len(y)+1)]

for i in range(len(x)+1):
    co[0][i] = i
for i in range(len(y)+1):
    co[i][0] = i

for i in range(len(y)):
    for j in range(len(x)):
        count = 0
        if x[j] != y[i]:
            count += 1
        co[i+1][j+1] = min(co[i][j]+count, co[i+1][j]+1, co[i][j+1]+1)

print(co[len(y)][len(x)])

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

for i in range(len(s1) + 1):
    dp[0][i] = i
for i in range(len(s2) + 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[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(s2)][len(s1)])

Solution (Python):
"""
17D8101031C 杉山　祥吾 ID:keisei334 python
"""

def levenshtein(s1, s2):
    n=len(s1)
    m=len(s2)
    dp = [[0]*(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]:
                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[n][m]

    
s1 = input()
s2 = input()

print(levenshtein(s1, s2))

"""実行結果

"""

Solution (Python):
def edit(s1,s2):
    
    n, m = len(s1), len(s2)
    E= [[0] * (m+1) for i in range(n+1)]
    
    for i in range(n+1):
        E[i][0] = i

    for j in range(m+1):
        E[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
            E[i][j] = min(E[i-1][j] + 1, E[i][j-1]+1, E[i-1][j-1] + cost)
            
    return E[n][m]

s1=input()
s2=input()

print(edit(s1,s2))

Solution (Python):
str1=input()
str2=input()

str1_len=len(str1)+1
str2_len=len(str2)+1

co=[[0 for j in range(str2_len)]for i in range(str1_len)]

for i in range(str1_len):
    co[i][0]=i
for j in range(str2_len):
    co[0][j]=j

for i in range(1,str1_len):
    for j in range(1,str2_len):
        if str1[i-1]==str2[j-1]:
            co[i][j]=co[i-1][j-1]
        else:
            co[i][j]=min(co[i-1][j-1],co[i-1][j],co[i][j-1])+1
print(co[str1_len-1][str2_len-1])

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

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

dp = [[0]*(len(s2)+1) for i 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):
        tmp = dp[i-1][j-1]
        if s1[i-1] != s2[j-1]:
            tmp += 1

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

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

Solution (Python):
s=input()
t=input()
n=len(s)
m=len(t)
dp=[[100000]*(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<=n:
            if dp[i+1][j]>dp[i][j]:
                dp[i+1][j]=dp[i][j]+1
        if j+1<=m:
            if dp[i][j+1]>dp[i][j]:
                dp[i][j+1]=dp[i][j]+1
        if i+1<=n and j+1<=m:
            if s[i]==t[j]:
                if dp[i+1][j+1]>dp[i][j]:
                    dp[i+1][j+1]=dp[i][j]
            else:
                if dp[i+1][j+1]>dp[i][j]:
                    dp[i+1][j+1]=dp[i][j]+1
print(dp[n][m])

Solution (Python):




s1 = input()
s2 = input()

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

Solution (Python):
X = input()
Y = input()
m = len(X)
n = len(Y)
res=[[m + n for j in range(n + 1)] for i in range(m + 1)]
for i in range(m + 1):
    res[i][0] = i
for j in range(n + 1):
    res[0][j] = j
for i in range(1,m+1):
    for j in range(1,n+1):
        a=1
        if X[i-1]==Y[j-1]:
            a=0
        res[i][j]=min(a+res[i-1][j-1], 1+res[i-1][j], 1+res[i][j-1])
print(res[m][n])

Solution (Python):
s1 = input()
s2 = input()
l1 = len(s1)
l2 = len(s2)
mat = [[float('inf') 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 i in range(l2):
    for j in range(l1):
        m = mat[i][j] + 1 if s1[j] != s2[i] else mat[i][j]
        mat[i+1][j+1] = min(m, mat[i][j+1] + 1, mat[i+1][j] + 1)
print(mat[l2][l1])

Solution (Python):
def ed(x, y):
    if len(x) > len(y):
        x, y = y, x
    nx, ny = len(x), len(y)
    dp = [[0] * (nx+1) for _ in range(ny+1)]

    for i in range(1, ny+1):
        dp[i][0] = i
        if i < nx+1: dp[0][i] = i
    
    for i in range(1, ny+1):
        for t in range(1, nx+1):
            dp[i][t] = min(dp[i-1][t-1]+(x[t-1]!=y[i-1]), dp[i-1][t]+1, dp[i][t-1]+1)

    return dp[-1][-1]

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

Solution (Python):
def main():
    S = input()
    T = input()
    N = len(S)
    M = len(T)
    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(N):
        for j in range(M):
            if S[i] == T[j]:
                dp[i+1][j+1] = min(dp[i][j], dp[i+1][j] + 1, dp[i][j+1] + 1)
            else:
                dp[i+1][j+1] = min(dp[i][j], dp[i+1][j], dp[i][j+1]) + 1
    print(dp[N][M])


if __name__ == '__main__':
    main()

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

dp = [[1010] * (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)):
        cost = 0 if s1[i] == s2[j] else 1
        dp[i + 1][j + 1] = min(dp[i + 1][j] + 1, dp[i][j + 1] + 1, dp[i][j] + cost)

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