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: Wrong Answer

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

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

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

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

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

Submission status: Wrong Answer

Solution code:
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:
        if j == 0:
            if s1[i] == s2[j]:
                x[i][j] = 0
            else:
                x[i][j] = 1
        else:
            x[i][j] = x[i][j-1] + 1
    elif j == 0:
        x[i][j] = x[i-1][j] + 1
    elif s1[i] == s2[j]:
        x[i][j] = x[i-1][j-1]
    elif i == j:
        x[i][j] = x[i-1][j-1] + 1
    elif j > i:
        x[i][j] = x[i][j-1] + 1
    else:
        x[i][j] = 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])

Submission status: Wrong Answer

Solution code:
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] = x[i-1][j-1]
    else:
        x[i][j] = min(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])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:

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



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

Submission status: Wrong Answer

Solution code:
def LD(str1,str2):
    A = [1 for _ in range(len(str2)+1)]
    for i in range(len(str1)):
        A[0] = i
        A_copy = A[:]
        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)

Submission status: Wrong Answer

Solution code:
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):
        for j in range(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))

Submission status: Wrong Answer

Solution code:
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)):
        f[i][0]=i
    for j in range(len(Y)):
        f[0][j]=j
    for i in range(len(X)+1):
        for j in range(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))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
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(1,len(Y)+1):
        f[0][j]=j
    for i in range(1,len(X)+1):
        for j in range(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))

Submission status: Wrong Answer

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



x = input()
y = input()
if len(x)>len(y):
    print(len(x)-L_common(x,y))
else:
    print(len(y)-L_common(x,y))

Submission status: Wrong Answer

Solution code:
#dj 16D8101012J ito jun
import sys
def search(a,b):
    na=len(a)
    nb=len(b)
    array = [[0]*(nb+1) for _ in range(na+1)]
    for i in range(na):
        array[i][0]=i
    for j in range(nb):
        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]
            elif prerow[j] > row[j-1]:
                row[j] = row[j-1]+1
            else:
                row[j] = prerow[j]+1
    return array[-1][-1]

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

Submission status: Wrong Answer

Solution code:
#dj 16D8101012J ito jun
import sys
def search(a,b):
    na=len(a)
    nb=len(b)
    array = [[0]*(nb+1) for _ in range(na+1)]
    for i in range(na):
        array[i][0]=i
    for j in range(nb):
        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))

Submission status: Wrong Answer

Solution code:
#dj 16D8101012J ito jun
import sys
def search(a,b):
    na=len(a)
    nb=len(b)
    array = [[0]*(nb) for _ in range(na)]
    for i in range(na):
        array[i][0]=i
    for j in range(nb):
        array[0][j]=j
    for i,x in enumerate(a):
        prerow=array[i-1]
        row=array[i]
        for j,y in enumerate(b):
            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))

Submission status: Wrong Answer

Solution code:
def search(a,b):
    na=len(a)
    nb=len(b)
    array = [[0]*(nb+1) for _ in range(na+1)]
    for i in range(na):
        array[i][0]=i
    for j in range(nb):
        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
    #pprint(array)
    return array[-1][-1]

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

Submission status: Wrong Answer

Solution code:
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):
    for j in range(1, len(s_2)+1):
        if not flag[i][j]:
            flag[i][j] = True
            if i == j:
                if s_1[i-1] == s_2[j-1]:
                    memo[i][j] = memo[i-1][j-1]
                else:
                    memo[i][j] = memo[i-1][j-1] + 1
            else:
                a = max(i-j, j-i)
                b = min(i, j)
                memo[i][j] = memo[b][b] + a

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

Submission status: Wrong Answer

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

# ababa
# babab

Submission status: Wrong Answer

Solution code:
def main():
    X=input()
    Y=input()
    dp=[]
    for y in range(len(Y)):
        now=0
        for i  in range(len(dp)):
            d=dp[i]
            if Y[y] in X[now:d]:
                dp[i]=now+X[now:d].index(Y[y])
            now=d+1
        if Y[y] in X[now:]:
            dp.append(now+X[now:].index(Y[y]))
    return max(len(X),len(Y))-len(dp)
print(main())

Submission status: Wrong Answer

Solution code:
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[x][1+y]+1,dp[x][1+y]+1,dp[x][y]+cost)
print(dp[len(X)][len(Y)])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
#?????????http://ja.wikipedia.org/wiki/??¬??????????????\??????????????¢
def levenshtein_distance(str1, str2):
    d = [[0] * (len(str2)) for _ in range(len(str1))]

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

    for i1 in range(1, len(str1)):
        for i2 in range(1, len(str2)):
            cost = 0 if str1[i1] == str2[i2] else 1
            d[i1][i2] = min(d[i1 - 1][i2    ] + 1,     # ??????????????\
                            d[i1    ][i2 - 1] + 1,     # ???????????????
                            d[i1 - 1][i2 - 1] + 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))

Submission status: Wrong Answer

Solution code:
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] + 1, dp[i][j] + 1 * (s1[i] != s2[j]))
print(dp[len(s1)][len(s2)])

Submission status: Wrong Answer

Solution code:
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):
    for j in xrange(l2):
        dp[i+1][j] = min(dp[i][j]+1, dp[i+1][j])
        dp[i][j+1] = min(dp[i][j]+1, dp[i][j+1])
        dp[i+1][j+1] = min(dp[i][j] + (s1[i]!=s2[j]), dp[i+1][j+1])
print dp[l1][l2]

Submission status: Wrong Answer

Solution code:
# Edit Distance
def ED():
    X = " " + input()
    Y = " " + input()
    ed = [[0]*(len(X)) for _ in range(len(Y))]
    for j in range(len(X)):
        for i in range(len(Y)):
            if (i == j == 0):
                continue
            if (X[j] == Y[i]):
                ed[i][j] = ed[i-1][j-1]
            else:
                if(j > i):
                    ed[i][j] = ed[i][j-1] + 1
                elif(j < i):
                    ed[i][j] = ed[i-1][j] + 1
                elif(j == i):
                    ed[i][j] = ed[i-1][j-1] + 1
    return ed[len(Y)-1][len(X)-1]

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

Submission status: Wrong Answer

Solution code:
# Edit Distance
def ED():
    X = " " + input()
    Y = " " + input()
    ed = [[0]*(len(X)) for _ in range(len(Y))]
    for j in range(len(X)):
        for i in range(len(Y)):
            if (i == j == 0):
                continue
            if (X[j] == Y[i]):
                ed[i][j] = ed[i-1][j-1]
            else:
                if(j > i):
                    ed[i][j] = ed[i][j-1] + 1
                elif(j < i):
                    ed[i][j] = ed[i-1][j] + 1
                elif(j == i):
                    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())

Submission status: Wrong Answer

Solution code:
import sys

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

memo = [[0 for x in range(len(s1)+1)] for y in range(len(s2)+1)]

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] + 1
        else:
            memo[i+1][j+1] = max(memo[i][j+1], memo[i+1][j])

print max(len(s1),len(s2)) - memo[-1][-1]

Submission status: Wrong Answer

Solution code:
import sys

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

memo = [[0 for x in range(len(s1)+1)] for y in range(len(s2)+1)]

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]

Submission status: Wrong Answer

Solution code:
s1 = input()
s2 = input()
if len(s1) < len(s2):
    s1, s2 = s2, s1
length = len(s2)
dp = {(s1, 0): 0}

for i in range(len(s1)):
    _dp = dict()
    for key, n in dp.items():
        #print(key, n)
        s, i = key
        if length <= i:
            _dp[(s[:-1], i)] = n+1
        elif s[i] == s2[i]:
            _dp[(s, i+1)] = n
        else:
            s_mod1 = s[:i] + s2[i] + s[i+1:]
            s_mod2 = s[:i] + s[i+1:]
            _dp[(s_mod1, i+1)] = n+1
            if len(s_mod2) >= length:
                _dp[(s_mod2, i)] = n+1
    dp = _dp
print(dp[(s2, length)])

Submission status: Wrong Answer

Solution code:
s1 = input()
s2 = input()
if len(s1) < len(s2):
    s1, s2 = s2, s1
length = len(s2)
dp = {(s1, 0): 0}
result = float("inf")

while dp:
    hoge = []
    append = hoge.append
    for key, n in dp.items():
        #print(key, n)
        s, i = key
        if s == s2:
            result = n if n < result else result
        elif length <= i:
            append((s[:-1], i, n+1))
        elif len(s) == i:
            append((s+s2[i], i+1, n+1))
        elif s[i] == s2[i]:
            append((s, i+1, n))
        else:
            s_mod1 = s[:i] + s2[i] + s[i+1:]
            s_mod2 = s[:i] + s[i+1:]
            append((s_mod1, i+1, n+1))
            append((s_mod2, i, n+1))
    dp = dict()
    for a, b, c in hoge:
        key = (a, b)
        if key not in dp or dp[key] > c:
            dp[key] = c
    #print(dp)
print(result)

Submission status: Wrong Answer

Solution code:
n = input()
m = input()
ln = len(n)
lm = len(m)
dp = [list(range(lm+1)) for i 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][j]+1, dp[i-1][j-1]+1)
print(dp[-1][-1])

Submission status: Wrong Answer

Solution code:
def ans(n, m):
    ln = len(n)
    lm = len(m)
    dp = [list(range(lm+1)) for i 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][j]+1, dp[i-1][j-1]+1)
    return dp[-1][-1]
n = input()
m = input()
print(ans(n, m))

Submission status: Wrong Answer

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

    for i in range(1, len(str1)):
        for j in range(1, len(str2)):
            val = dp[i-1][j-1] if str1[i] == str2[j] 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))

Submission status: Time Limit Exceeded

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: Time Limit Exceeded

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

for i in range(1,len(list1)+1):
	list_d[i][0]=i
for i in range(1,len(list2)+1):
	list_d[0][i]=i
	
	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: Time Limit Exceeded

Solution code:
s1 = input()
s2 = input()
if len(s1) < len(s2):
    s1, s2 = s2, s1
length = len(s2)
dp = {(s1, 0): 0}
result = float("inf")

while dp:
    hoge = []
    append = hoge.append
    for key, n in dp.items():
        #print(key, n)
        s, i = key
        if s == s2:
            result = n if n < result else result
        elif length <= i:
            append((s[:-1], i, n+1))
        elif len(s) == i:
            append((s+s2[i], i+1, n+1))
        elif s[i] == s2[i]:
            append((s, i+1, n))
        else:
            s_mod1 = s[:i] + s2[i] + s[i+1:]
            s_mod2 = s[:i] + s[i+1:]
            s_mod3 = s[:i] + s2[i] + s[i:]
            append((s_mod1, i+1, n+1))
            append((s_mod2, i, n+1))
            append((s_mod3, i+1, n+1))
    dp = dict()
    for a, b, c in hoge:
        key = (a, b)
        if key not in dp or dp[key] > c:
            dp[key] = c
    #print(dp)
print(result)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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)
                       #insert       delete?     change?
        else:
            f[i][j]=f[i-1][j-1]
print(f[i][j])

Submission status: Accepted

Solution code:



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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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)

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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 p[m]


X=input()
Y=input()

print(search(X,Y))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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
    #pprint(array)
    return array[-1][-1]

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

Submission status: Accepted

Solution code:

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

Submission status: Accepted

Solution code:
def levenshtein(str1, str2):
    if len(str1) == 0 or len(str2) == 0: return max(len(str1), len(str2))
    # init
    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))

Submission status: Accepted

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

Submission status: Accepted

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