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



Sample input:
acac
acm


Sample output:
2

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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)])

Submission status: Accepted

Solution code:
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)}")

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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
#for i in range(n+1):
#    print(Dp[i])
print(Dp[l1][l2])

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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)])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

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[i][j] := T[0..j]をS[0..i]にするのにかかる最小操作数
dp = [[INF] * (M+1) for i in range(N+1)]
# 初期化(Sが0文字でTも0文字なら何もしなくていい)
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])
# SがN文字、TがM文字で終わる場合の最小回数
print(dp[N][M])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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[j][i] == the distance between s1[:i] and s2[:j]
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
import sys
def main(argv):
    args = sys.argv
    # file_name = args[1]
    # f = open(file_name, 'r')
    # s1 =  f.readline().strip()
    # s2 =  f.readline().strip()

    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
    # for l in dp:
    #     print(l)
    print(dp[n1][n2])
if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
#レーベンシュタイン距離

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])

Submission status: Accepted

Solution code:
# N,M = map(int, input().split())
s1 = input()
s2 = input()
N = len(s1)
M = len(s2)
inf = float("inf")

dp = [ [inf] * (M+1) for _ in range(N+1)]
# dp[0][0] = 0 # dp[n][m] # s1$B$r(Bn$BJ8;zL\$^$G!"(Bs2$B$r(Bm$BJ8;zL\$^$G8+$?$H$-$N:G>.JT=8%3%9%H(B

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)
print(dp[N][M])

Submission status: Accepted

Solution code:
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)])

Submission status: Accepted

Solution code:
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 = 999
inf = 1 << 60
s1 = input()
s2 = input()
max1 = len(s1)
max2 = len(s2)

# dp[i1][i2] = s1のi1文字目とs2のi2文字目までの編集距離
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])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000)

def my_ed(s,t):
    #print('call',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
        #print(i,j,s[:i+1],t[:j+1],res)
        return res
     
    return dp(len(s)-1,len(t)-1)
 
 
print(my_ed(input(),input()))

Submission status: Accepted

Solution code:
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[s][t]
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])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# DPL_1_E: Combinatorial - Edit Distance (Levenshtein Distance)
# D[i][j] = if s1[i] == s2[j]: D[i-1][j-1]
#           else: min(D[i-1][j-1], D[i-1][j], D[i][j-1]) + 1


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()

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
def edit_distance(a,b):
    n = len(a)
    m = len(b)
    L = [i for i in range(m+1)] #0행  (i행j열 요소:)
    for i in range(1,n+1):
        copy = L[:]     ##(i-1)행
        L[0] = i   ## i행 0열 (초기값) 값 설정
        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))

Submission status: Accepted

Solution code:
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)])

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

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

#dp[j][i] = (s1のi文字目までとs2のj文字目までの距離)
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)])

Submission status: Accepted

Solution code:
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])

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <string>
int mini(int x,int y){
  if(x<y){
    return x;
  }else{
    return y;
  }
}
 
int main() {
  std::string str1,str2;
  int A[1001][1001];
  int gap;
  std::cin>>str1;
  std::cin>>str2;
  for(int i=0;i<=str1.size();i++){
    A[0][i]=i;
  }
  for(int i=0;i<=str2.size();i++){
    A[i][0]=i;
  }
  for(int i=1;i<=str1.size();i++){
    for(int j=1;j<=str2.size();j++){
      if(str1[i-1]==str2[j-1]){
	gap=0;
      }else{
	gap=1;
      }
      A[i][j]=mini(A[i-1][j-1]+gap,mini(A[i-1][j]+1,A[i][j-1]+1+1));
      //std::cout<<A[i][j]<<" ";
    }
    //std::cout<<"\n";
  }
  std::cout<<A[str1.size()][str2.size()]<<"\n";
  return 0;
 
}

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <string>
int mini(int x,int y){
  if(x<y){
    return x;
  }else{
    return y;
  }
}
 
int main() {
  std::string str1,str2;
  int A[1001][1001];
  int gap;
  std::cin>>str1;
  std::cin>>str2;
  for(int i=0;i<str1.size();i++){
    A[i][0]=i;
  }
  for(int i=0;i<str2.size();i++){
    A[0][i]=i;
  }
  /*
  for(int i=0;i<str1.size();i++){
    for(int j=0;j<str2.size();j++){
      std::cout<<A[i][j]<<" ";
    }
    std::cout<<"\n";
  }
  */
  for(int i=1;i<=str1.size();i++){
    for(int j=1;j<=str2.size();j++){
      if(str1[i-1]==str2[j-1]){
	gap=0;
      }else{
	gap=1;
      }
      A[i][j]=mini(A[i-1][j-1]+gap,mini(A[i-1][j]+1,A[i][j-1]+1));
      //std::cout<<A[i-1][j-1]<<" ";
    }
    //std::cout<<"\n";
  }
  if(str1.size()>str2.size()){
    A[str1.size()-1][str2.size()-1]+=str1.size()-str2.size();
  }else{
    A[str1.size()-1][str2.size()-1]+=str2.size()-str1.size();
  }
  std::cout<<A[str1.size()-1][str2.size()-1]<<"\n";
  return 0;
 
}

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <string>
int mini(int x,int y){
  if(x<y){
    return x;
  }else{
    return y;
  }
}
 
int main() {
  std::string str1,str2;
  int A[1001][1001];
  int gap;
  std::cin>>str1;
  std::cin>>str2;
  for(int i=0;i<str1.size();i++){
    A[i][0]=i;
  }
  for(int i=0;i<str2.size();i++){
    A[0][i]=i;
  }
  /*
  for(int i=0;i<str1.size();i++){
    for(int j=0;j<str2.size();j++){
      std::cout<<A[i][j]<<" ";
    }
    std::cout<<"\n";
  }
  */
  for(int i=1;i<=str1.size();i++){
    for(int j=1;j<=str2.size();j++){
      if(str1[i-1]==str2[j-1]){
	gap=0;
      }else{
	gap=1;
      }
      A[i][j]=mini(A[i-1][j-1]+gap,mini(A[i-1][j]+1,A[i][j-1]+1));
      //std::cout<<A[i-1][j-1]<<" ";
    }
    //std::cout<<"\n";
  }
  if(str1.size()>str2.size()){
    A[str1.size()-1][str2.size()-1]+=str1.size()-str2.size();
  }else{
    A[str1.size()-1][str2.size()-1]+=str2.size()-str1.size();
  }
  if(str1.size()>str2.size()){
     std::cout<<A[str1.size()-1][str2.size()-1]<<"\n";
  }else{
    std::cout<<A[str1.size()][str2.size()]<<"\n";
  }
  return 0;
 
}

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <string>
int mini(int x,int y){
  if(x<y){
    return x;
  }else{
    return y;
  }
}
 
int main() {
  std::string str1,str2;
  int A[1001][1001];
  int gap;
  std::cin>>str1;
  std::cin>>str2;
  for(int i=0;i<=str1.size();i++){
    A[i][0]=i;
  }
  for(int i=0;i<=str2.size();i++){
    A[0][i]=i;
  }
  /*
  for(int i=0;i<str1.size();i++){
    for(int j=0;j<str2.size();j++){
      std::cout<<A[i][j]<<" ";
    }
    std::cout<<"\n";
  }
  */
  for(int i=1;i<=str1.size();i++){
    for(int j=1;j<=str2.size();j++){
      if(str1[i-1]==str2[j-1]){
	gap=0;
      }else{
	gap=1;
      }
      A[i][j]=mini(A[i-1][j-1]+gap,mini(A[i-1][j]+1,A[i][j-1]+1));
      //std::cout<<A[i-1][j-1]<<" ";
    }
    //std::cout<<"\n";
  }
  if(str1.size()>str2.size()){
    A[str1.size()-1][str2.size()-1]+=str1.size()-str2.size();
  }else{
     A[str1.size()-1][str2.size()-1]+=str2.size()-str1.size();
  }

  if(str1.size()>str2.size() and A[str1.size()][str2.size()]!=1){
    std::cout<<A[str1.size()-1][str2.size()-1]<<"\n";
  }else{
    std::cout<<A[str1.size()][str2.size()]<<"\n";
  }
  return 0;
 
}

Submission status: Runtime Error

Solution code:

list1=list(input())
list2=list(input())
cost=0

list_d=[[0 for i in range(len(list2)+1)] for j in range(list1)+1]

for i in range(1,len(list1)+1):
	list_d[i][0]=i
for j in range(1,len(list2)+1):
	list_d[0][j]=j
	
	for i in range(1,len(list1)+1):
		for j in range(1,len(list2)+1):
			if list1[i-1]!=list2[j-1]:
				cost=1
			else:
				cost=0
			
			list_d[i][j]=min(list_d[i-1][j-1]+cost,list_d[i-1][j]+1,list_d[i][j-1]+1)
			
print(list_d[len(list1)][len(list2)])

Submission status: Runtime Error

Solution code:

list1=list(input())
list2=list(input())
cost=0

list_d=[[0 for i in range(len(list2)+1)] for j in range(len(list1))+1]

for i in range(1,len(list1)+1):
	list_d[i][0]=i
for j in range(1,len(list2)+1):
	list_d[0][j]=j
	
	for i in range(1,len(list1)+1):
		for j in range(1,len(list2)+1):
			if list1[i-1]!=list2[j-1]:
				cost=1
			else:
				cost=0
			
			list_d[i][j]=min(list_d[i-1][j-1]+cost,list_d[i-1][j]+1,list_d[i][j-1]+1)
			
print(list_d[len(list1)][len(list2)])

Submission status: Runtime Error

Solution code:
list1=list(input())
list2=list(input())

list_d=[[0 for i in range(len(list2)+1)] for j in range(len(list1)+1)]

list_d[1][0]=1
list_d[0][1]=1
	
	for i in range(1,len(list1)+1):
		for j in range(1,len(list2)+1):
			list_d[i][0]=i
			list_d[0][j]=j
			if list1[i-1]!=list2[j-1]:
				cost=1
			else:
				cost=0
			
			list_d[i][j]=min(list_d[i-1][j-1]+cost,list_d[i-1][j]+1,list_d[i][j-1]+1)
			
print(list_d[len(list1)][len(list2)])

Submission status: Runtime Error

Solution code:
n = int(input())

cnt=[0 for i in range(n)]

for i in range(n):
	A = []
	A = input()
	B = []
	B = input()

	DP = [[0 for k in range(len(B)+1)] for j in range(len(A)+1)]

	for j in range(len(A)+1):
		DP[j][0]=j

	for k in range(len(B)+1):
		DP[0][k]=k

	for j in range(len(A)):
		for k in range(len(B)):
			if A[j]==B[k]:
				DP[j+1][k+1]=DP[j][k]
			else:
				DP[j+1][k+1]=min(DP[j+1][k], DP[j][k+1], DP[j][k])+1
	cnt[i]=DP[len(A)][len(B)]

for i in range(n):
	print(cnt[i])

Submission status: Runtime Error

Solution code:
import numpy as np

x=input()
y=input()
if(x==y): #同じなら０を出力して終了
   print(0)
   exit()

list = np.zeros((len(y)+1,len(x)+1))

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

for i in range(1,len(y)+1):
   for j in range(1,len(x)+1):
      a=list[i-1][j-1]
      b=list[i][j-1]+1
      c=list[i-1][j]+1
      if not(x[j-1] == y[i-1]):
         a=a+1
      list[i][j]=min(a,b,c)

print(int(list[len(y)][len(x)]))

Submission status: Runtime Error

Solution code:
import numpy

x=input()
y=input()
if(x==y): #同じなら０を出力して終了
   print(0)
   exit()

list = numpy.zeros((len(y)+1,len(x)+1))

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

for i in range(1,len(y)+1):
   for j in range(1,len(x)+1):
      a=list[i-1][j-1]
      b=list[i][j-1]+1
      c=list[i-1][j]+1
      if not(x[j-1] == y[i-1]):
         a=a+1
      list[i][j]=min(a,b,c)

print(int(list[len(y)][len(x)]))

Submission status: Runtime Error

Solution code:
def L_common(str1,str2):
    d = [0 for i in range(len(str2)+1)]
    
    for n1 in str1:
        tmp = d[:]
        for (j,n2) in enumerate(str2):
            if n1 == n2:
                d[j+1] = tmp[j]+1
            elif d[j+1]<d[j]:
                d[j+1] = d[j]
    return d[len(str2)]

n = int(input())
stock = []
for i in range(n):
    x = input()
    y = input()
    if len(x)>len(y):
        stock.append(len(x)-L_common(x,y))
    else:
        stock.append(len(y)-L_common(x,y))

for i in stock:
    print(i)

Submission status: Runtime Error

Solution code:
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 pre[m]


X=input()
Y=input()

print(search(X,Y))

Submission status: Runtime Error

Solution code:
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(len(a)+1):
		for j in range(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])

Submission status: Runtime Error

Solution code:
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(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])

Submission status: Runtime Error

Solution code:
# python template for atcoder1
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]+1, dp[j][k-1])
            if s1[j-1] == s2[k-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)

Submission status: Runtime Error

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

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