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:
import sys
fin = sys.stdin.readline

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

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

# prefix dp
# dp[i][j] is the edit distance between x[i:] and y[j:].
dp = [[0] * (len(s2) + 1) for _ in range(len_s1 + 1)]

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

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

print(dp[0][0])

Submission status: Accepted

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

Submission status: Accepted

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


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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Combinatorial - Edit Distance (Levenshtein Distance)
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_E&lang=jp

"""
import sys


def solve(word1, word2):
    n, m = len(word1), len(word2)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        dp[i][0] = i
    for j in range(m + 1):
        dp[0][j] = j

    for i in range(1, n + 1):
        for j in range(1, m + 1):
            cost = 0 if word1[i - 1] == word2[j - 1] else 1
            dp[i][j] = min(dp[i - 1][j] + 1,         # insertion
                           dp[i][j - 1] + 1,         # deletion
                           dp[i - 1][j - 1] + cost)  # replacement
    return dp[n][m]


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


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

Submission status: Accepted

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], 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: Accepted

Solution code:
import sys

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

Submission status: Accepted

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

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

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

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

print(delta(s1, s2))

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

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

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

    return dp[l1][l2]


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

Submission status: Accepted

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

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

    return prev_dp[-1]


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

Submission status: Accepted

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

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

    return prev_dp[-1]


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

Submission status: Accepted

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

Submission status: Accepted

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

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

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

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

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
acac
acm

output:
2
"""

import sys


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

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

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

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

    return dp[-1][-1]


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

Submission status: Accepted

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

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

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

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

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

print dp[m][n]

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys

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

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

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

print memo[-1][-1]

Submission status: Accepted

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

print(dp[s1len][s2len])

Submission status: Accepted

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

# solve
s1 = input()
s2 = input()

ans = levenshtein(s1, s2)

print(ans)

Submission status: Accepted

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

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

print(dp[s1_len][s2_len])

Submission status: Accepted

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


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

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

    return current[-1]

print(levenshtein(s1, s2))

Submission status: Accepted

Solution code:
def levenshtein(s1, s2):
    n, m = len(s1), len(s2)
    dp = [[0] * (m+1) for _ in range(n+1)]
    
    for i in range(n+1):
        dp[i][0] = i
    
    for j in range(m+1):
        dp[0][j] = j

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

s1 = input()
s2 = input()

print(levenshtein(s1, s2))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

s = input()
t = input()

print(edit_dist(s,t))

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
s = list(input())
n = len(s)
t = list(input())
m = len(t)
dp = [[0] * (m+1) for _ in range(n+1)]

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

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

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

print(dp[n][m])

Submission status: Accepted

Solution code:
def main():
    import sys

    readline = sys.stdin.readline

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

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

    # 配るDP
    # dp[i][j]はi文字目までの文字列s1とj文字目までの文字列s2の編集距離
    inf = 10 ** 3
    dp = [[inf] * (ls2 + 1) for _ in [0] * (ls1 + 1)]
    for i in range(ls1 + 1):
        dp[i][0] = i
    for j in range(ls2 + 1):
        dp[0][j] = j

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


main()

Submission status: Accepted

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

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

#print('      '+', '.join(list(s2)))
#for i,v in enumerate(dp):
    #if i != 0:
        #print(s1[i-1], v)
        #continue
    #print(' ', v)
print(dp[len(s1)][len(s2)])

Submission status: Accepted

Solution code:
import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

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

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


# ===CODE===


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

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

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

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

    print(dp[s2_l][s1_l])


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

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

print(dp[ly][lx])

Submission status: Accepted

Solution code:
s = input()
t = input()
ls, lt = len(s), len(t)

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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)]
# 初期化：dp[0][i] = i
ans[0][0] = 0

# ans[i][j]:= s1のi文字目、s2のj文字目を一致させた時のmin編集距離
# ans[i][j] = min(ans[i-1][j],ans[i][j-1],match+ans[i-1][j-1])
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])
#print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

#dp[i][j] := s_1の左からiまでとs_2の左からjまでで最大の連続共通部分列の長さ
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)])

Submission status: Accepted

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

Submission status: Accepted

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

#for i in range(len_1 + 1):
#	print(dp[i])

print(dp[len_1][len_2])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
x=input() #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]) #xのi文字目とyの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])

Submission status: Accepted

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