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:
def levenshteinDistance(s1: str, s2: str):
    n = len(s1)
    m = len(s2)
    dp = [[0] * (n + 1) for i in range(m + 1)]

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

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

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

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

Submission status: Accepted

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

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

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

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

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

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

Submission status: Accepted

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

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

    return dp[m][n]

s1 = input()
s2 = input()

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

Submission status: Accepted

Solution code:
A = str(input())
n = len(A)
B = str(input())
m = len(B)
#dp[i][j], Aがi文字目、Bがj文字目までにおける最小処理回数
INF = float("inf")
dp = [[INF]*(m+1) for _ in range(n+1)]
#初期化の方法が特殊。片方が0でもう片方がi文字なら最小処理回数はi。
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): #i = 0つまり、0文字目なのでdp[1][1]からスタート
  for j in range(m):
    if A[i] == B[j]: #同じ場合そのままか、片方が一つずれているところから追加挿入。
      dp[i+1][j+1] = min(dp[i][j],dp[i][j+1]+1,dp[i+1][j]+1)
    else: #異なる場合i文字目を交換か、片方が一つずれているところから追加挿入。
      dp[i+1][j+1] = min(dp[i][j]+1,dp[i][j+1]+1, dp[i+1][j]+1)
print(dp[n][m])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# n,m = map(int,sys.stdin.readline().split())
# a = list(map(int,sys.stdin.readline().split()))
# a = [sys.stdin.readline() for s in range(n)]
# s = sys.stdin.readline().rstrip()
# n = int(sys.stdin.readline())
import sys,bisect
sys.setrecursionlimit(15000)

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

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

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

Submission status: Accepted

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

Submission status: Accepted

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

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

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

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

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

for i in range(1, n+1):
    for j in range(1, m+1):
        c = 0 if s1[i-1] == s2[j-1] else 1
        DP[i][j] =  min(DP[i-1][j] + 1, # insertion
                        DP[i][j-1] + 1, # deletion
                        DP[i-1][j-1] + c)   # replacement/nop

print DP[n][m]

Submission status: Accepted

Solution code:
S = input()
T = input()
# S = 'acac'
# T = 'acm'
# DP[i][j]=Sのi文字とTのj文字の編集距離
DP = [[0 for j in range(len(T)+1)] for i in range(len(S)+1)]
for i in range(len(S)+1):
    DP[i][0] = i
for j in range(len(T)+1):
    DP[0][j] = j
for i in range(1, len(S)+1):
    for j in range(1, len(T)+1):
        if S[i-1] == T[j-1]:
            c = 0
        else:
            c = 1
        DP[i][j] = min(DP[i-1][j]+1, DP[i][j-1]+1, DP[i-1][j-1]+c)
print(DP[len(S)][len(T)])

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
s=input()
t=input()
n,m=len(s),len(t)
if n==0:
    print(m)
    exit()
if m==0:
    print(n)
    exit()
pre=[i for i in range(m+1)]
for i in range(n):
    nxt=list(range(m+1))
    nxt[0]=i+1
    for j in range(m):
        cost=0 if s[i]==t[j] else 1
        nxt[j+1]=min(pre[j+1]+1,nxt[j]+1,pre[j]+cost)
    pre,nxt=nxt,pre

print(pre[m])

Submission status: Accepted

Solution code:
import os
import sys

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

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


word = sys.stdin.buffer.readline().decode().rstrip()
input = sys.stdin.buffer.readline().decode().rstrip()
# dist[v][w]: input を v 文字、word を w 文字見たときの、それ以前の編集距離
dist = [[INF] * (len(word) + 1) for _ in range(len(input) + 1)]
dist[0] = list(range((len(word) + 1)))
for v in range(1, len(input) + 1):
    vc = input[v - 1]
    dist[v][0] = v
    for w in range(1, len(word) + 1):
        wc = word[w - 1]
        dist[v][w] = min(dist[v][w], dist[v - 1][w - 1] + (0 if vc == wc else 1))
        dist[v][w] = min(dist[v][w], dist[v][w - 1] + 1)
        dist[v][w] = min(dist[v][w], dist[v - 1][w] + 1)
print(dist[-1][-1])

Submission status: Accepted

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

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

print(levenshtein_distance(s1, s2))

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
# from fractions import gcd
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from functools import reduce
from bisect import bisect_left, insort_left
from heapq import heapify, heappush, heappop

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

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


class Levenshtein:
    def init_array(self, str1, str2):
        distance = []
        for i in range(len(str1)+1):
            distance.append([0] * (len(str2) + 1))
            distance[i][0] = i
        for j in range(len(str2)+1):
            distance[0][j] = j
        return distance

    def edit_dist(self, str1, str2, distance):
        dist = [0] * 3
        for i in range(1, len(str1)+1):
            for j in range(1, len(str2)+1):
                dist[0] = distance[i-1][j-1] if str1[i-1] == str2[j-1] else distance[i-1][j-1] + 1
                dist[1] = distance[i][j-1] + 1
                dist[2] = distance[i-1][j] + 1
                distance[i][j] = min(dist)
        return distance[i][j]

    def __init__(self, str1, str2):
        self.str1 = str1
        self.str2 = str2
        Levenshtein.distance = self.init_array(str1, str2)
        Levenshtein.dist = self.edit_dist(str1, str2, Levenshtein.distance)


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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

s1 = input()
s2 = input()

def EditDistance(S, T):
    dp = [[INF]*(len(T)+1) for _ in range(len(S)+1)]
    dp[0][0] = 0
    for i in range(-1, len(S)):
        for j in range(-1, len(T)):
            if i == -1 and j == -1:
                continue
            if i >= 0 and j >= 0:
                if S[i] == T[j]:
                    dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j])
                else:
                    dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j] + 1)
            if i >= 0:
                dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j+1] + 1)
            if j >= 0:
                dp[i+1][j+1] = min(dp[i+1][j+1], dp[i+1][j] + 1)
    return dp[len(S)][len(T)]

print(EditDistance(s1, s2))

Submission status: Accepted

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

a = input()
b = input()

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

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

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

Submission status: Accepted

Solution code:
import sys

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

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

def main():
    s=SI()
    t=SI()
    n=len(s)
    m=len(t)
    dp=[[0]*(m+1) for _ in range(n+1)]
    for i in range(n+1):dp[i][0]=i
    for j in range(m+1):dp[0][j]=j
    for i,c0 in enumerate(s):
        for j,c1 in enumerate(t):
            dp[i+1][j+1]=min(dp[i][j+1]+1,dp[i+1][j]+1,dp[i][j]+(c0!=c1))
    print(dp[n][m])

main()

Submission status: Accepted

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

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


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


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



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

Submission status: Accepted

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

def levenshtein_distance(x, y):
    lx = len(x); ly = len(y)
    dp = [[0 for i in range(ly + 1)] for j in range(lx + 1)]
    
    for i in range(lx + 1):
        dp[i][0] = i
    for j in range(1, ly + 1):
        dp[0][j] = j
        
    for i in range(1, lx + 1):
        for j in range(1, ly + 1):
            if x[i - 1] == y[j - 1]:
                cost = 0
            else:
                cost = 1
                
            dp[i ][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + cost)
    
    return dp[lx][ly]
    
print(levenshtein_distance(x, y))

Submission status: Accepted

Solution code:
#!python3

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

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

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

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

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
S1=input()
S2=input()
dp=[[0 for i in range(len(S1) + 1)]for j in range(len(S2)+1)]
for i in range(len(S1)+1):
    dp[0][i]=i
for j in range(len(S2)+1):
    dp[j][0]=j
for i in range(1,len(S1)+1):
    for j in range(1,len(S2)+1):
        if S1[i-1]==S2[j-1]:
            dp[j][i]=dp[j-1][i-1]
        else:
            dp[j][i]=min(dp[j-1][i],dp[j][i-1],dp[j-1][i-1])+1
print(dp[len(S2)][len(S1)])

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

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

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

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
"""
17D8101031C 杉山　祥吾 ID:keisei334 python
"""

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

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

    
s1 = input()
s2 = input()

print(levenshtein(s1, s2))

"""実行結果

"""

Submission status: Accepted

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

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

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

s1=input()
s2=input()

print(edit(s1,s2))

Submission status: Accepted

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

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

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

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

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

Submission status: Accepted

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

Submission status: Accepted

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

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

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

for i in range(1, len(s1)+1):
    for j in range(1, len(s2)+1):
        tmp = dp[i-1][j-1]
        if s1[i-1] != s2[j-1]:
            tmp += 1

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

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

Submission status: Accepted

Solution code:
s=input()
t=input()
n=len(s)
m=len(t)
dp=[[100000]*(m+1) for i in range(n+1)]
dp[0][0]=0
for i in range(n+1):
    for j in range (m+1):
        if i+1<=n:
            if dp[i+1][j]>dp[i][j]:
                dp[i+1][j]=dp[i][j]+1
        if j+1<=m:
            if dp[i][j+1]>dp[i][j]:
                dp[i][j+1]=dp[i][j]+1
        if i+1<=n and j+1<=m:
            if s[i]==t[j]:
                if dp[i+1][j+1]>dp[i][j]:
                    dp[i+1][j+1]=dp[i][j]
            else:
                if dp[i+1][j+1]>dp[i][j]:
                    dp[i+1][j+1]=dp[i][j]+1
print(dp[n][m])

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!


s1 = input()
s2 = input()

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

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
s1 = input()
s2 = input()
l1 = len(s1)
l2 = len(s2)
mat = [[float('inf') for _ in range(l1 + 1)] for _ in range(l2 + 1)]

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

for i in range(l2):
    for j in range(l1):
        m = mat[i][j] + 1 if s1[j] != s2[i] else mat[i][j]
        mat[i+1][j+1] = min(m, mat[i][j+1] + 1, mat[i+1][j] + 1)
print(mat[l2][l1])

Submission status: Accepted

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

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

    return dp[-1][-1]

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

Submission status: Accepted

Solution code:
def main():
    S = input()
    T = input()
    N = len(S)
    M = len(T)
    dp = [[0 for j in range(M+1)] for i in range(N+1)]
    for i in range(N+1):
        dp[i][0] = i
    for j in range(M+1):
        dp[0][j] = j

    for i in range(N):
        for j in range(M):
            if S[i] == T[j]:
                dp[i+1][j+1] = min(dp[i][j], dp[i+1][j] + 1, dp[i][j+1] + 1)
            else:
                dp[i+1][j+1] = min(dp[i][j], dp[i+1][j], dp[i][j+1]) + 1
    print(dp[N][M])


if __name__ == '__main__':
    main()

Submission status: Accepted

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

dp = [[1010] * (len(s2) + 1) for _ in range(len(s1) + 1)]
for i in range(len(s1) + 1):
    dp[i][0] = i
for j in range(len(s2) + 1):
    dp[0][j] = j

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

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

Submission status: Accepted

Solution code:
def edit_dist(S0, S1):
    i = len(S0)
    j = len(S1)
    dp = [i for i in range(len(S1) + 1)]

    for i in range(1, i+1):
        dp_prev = dp[:]
        dp[0] = i
        for j in range(1, j+1):
            dp[j] = min(dp_prev[j-1] + (S0[i-1] is not S1[j-1]), dp_prev[j] + 1, dp[j-1] + 1)
    return dp[-1]

if __name__ == "__main__":
    s0 = input()
    s1 = input()
    print(edit_dist(s0, s1))

Submission status: Accepted

Solution code:
S = list(input())
T = list(input())
dp = [[float('inf')]*(len(T)+1) for _ in range(len(S)+1)]
dp[0][0] = 0

for i in range(len(S)):
  dp[i+1][0] = i+1
for j in range(len(T)):
  dp[0][j+1] = j+1
for i in range(len(S)):
  a = S[i]
  for j in range(len(T)):
    b = T[j]
    dp[i+1][j+1] = min(dp[i+1][j]+1, dp[i][j+1]+1, dp[i][j]+(a != b))

print(dp[len(S)][len(T)])

Submission status: Accepted

Solution code:
def ld(s1, s2):
    l1 = len(s1)
    l2 = len(s2)
    if l1 == 0 and l2 == 0:
        return 0
    if l1 == 0:
        return l2
    if l2 == 0:
        return l1

    INF = 10**10
    DP = [[INF]*(l2+1) for _ in range(l1+1)] 
    for p1 in range(l1+1):
        DP[p1][0] = p1 
    for p2 in range(l2+1):
        DP[0][p2] = p2 

    for p1 in range(1,l1+1):
        for p2 in range(1,l2+1):
            if s1[p1-1] == s2[p2-1]:
                DP[p1][p2] = min(DP[p1][p2],DP[p1-1][p2-1])
            else:
                DP[p1][p2] = min(DP[p1][p2],DP[p1-1][p2]+1)
                DP[p1][p2] = min(DP[p1][p2],DP[p1][p2-1]+1)
                DP[p1][p2] = min(DP[p1][p2],DP[p1-1][p2-1]+1)
    return DP[l1][l2]

S1 = input() 
S2 = input() 
print(ld(S1,S2))

Submission status: Accepted

Solution code:
def main():
    s = input()
    t = input()
    n, m = len(s), len(t)
    dp = [[j if i == 0 else 10 ** 10 for i in range(m + 1)] for j in range(n + 1)]
    dp[0] = [i for i in range(m + 1)]
    for i in range(n):
        for j in range(m):
            dp[i + 1][j + 1] = min(dp[i][j + 1] + 1,
                                   dp[i + 1][j] + 1,
                                   dp[i][j] + 1 - (s[i] == t[j]))
    ans = dp[n][m]
    print(ans)


main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
INF = float("inf")


def main():
    s1 = input()[:-1]
    s2 = input()[:-1]
    S1 = len(s1)
    S2 = len(s2)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
INF = 10 ** 10

s1,s2 = input(),input()
n,m = len(s1),len(s2)
dp = [[INF] * (m + 1) for i in range(n + 1)]
dp[0][0] = 0
for i in range(n + 1):
	for j in range(m + 1):
		if i >= 1:
			dp[i][j] = min(dp[i][j],dp[i - 1][j] + 1)
		if j >= 1:
			dp[i][j] = min(dp[i][j],dp[i][j - 1] + 1)
		if i >= 1 and j >= 1:
			dp[i][j] = min(dp[i][j],dp[i - 1][j - 1] + (s1[i - 1] != s2[j - 1]))
print(dp[n][m])

Submission status: Accepted

Solution code:
s1 = input()
s2 = input()
dict = dict([])
s1_num = []
s2_num = []
for s in s1:
    if not s in dict:
        dict[s] = len(dict)
    s1_num.append(dict[s])
for s in s2:
    if not s in dict:
        dict[s] = len(dict)
    s2_num.append(dict[s])

s1_len = len(s1_num)
s2_len = len(s2_num)

lst = [[0] * (s2_len + 1) for _ in range(s1_len + 1)]
lst[0] = [i for i in range(s2_len + 1)]
for x in range(s1_len + 1):
    lst[x][0] = x

for i in range(1, s1_len + 1):
    for j in range(1, s2_len + 1):
        if s1_num[i - 1] == s2_num[j - 1]:
            lst[i][j] = min((lst[i - 1][j - 1]), (lst[i - 1][j] + 1), (lst[i][j - 1] + 1))
        else:
            lst[i][j] = min((lst[i - 1][j - 1] + 1), (lst[i - 1][j] + 1), (lst[i][j - 1] + 1))
print(lst[s1_len][s2_len])

Submission status: Accepted

Solution code:
s1=input()
s2=input()
mp=[[0]*(len(s1)+1) for _ in range(len(s2)+1)]
#この問題でも先に0を用意
for n in range(1,len(s2)+1):
    mp[n][0]+=mp[n-1][0]+1
for m in range(1,len(s1)+1):
    mp[0][m]+=mp[0][m-1]+1

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

Submission status: Accepted

Solution code:
s1 = input()
s2 = input()
l1 = len(s1)
l2 = len(s2)
mat = [[l1 + l2 for _ in range(l1 + 1)] for _ in range(l2 + 1)]

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

for j in range(l2):
    for i in range(l1):
        m = mat[j][i] + 1 if s1[i] != s2[j] else mat[j][i]
        mat[j+1][i+1] = min(m, mat[j][i+1] + 1, mat[j+1][i] + 1)
print(mat[l2][l1])

Submission status: Accepted

Solution code:
s1=input()
s2=input()
l1,l2=len(s1),len(s2)
dp=[[0]*(l2+1) for _ in range(l1+1)] #s1のi文字目、s2のj文字目までの編集距離をdp[i][j]とする
for i in range(l1+1):
    dp[i][0]=i
for j in range(l2+1):
    dp[0][j]=j
for i in range(1,l1+1):
    for j in range(1,l2+1):
        dp[i][j]=min(dp[i][j-1]+1,dp[i-1][j]+1,dp[i-1][j-1]+(s1[i-1]!=s2[j-1]))
print(dp[l1][l2])

Submission status: Accepted

Solution code:
# coding: utf-8
# s1, s2の入力
s1 = input()
s2 = input()
# メモ化
memo = [[i for i in range(len(s1) + 1)] if j == 0 else [j if i == 0 else -1 for i in range(len(s1) + 1)] for j in range(len(s2) + 1)]
for i in range(1, len(s2) + 1):
    for j in range(1, len(s1) + 1):
        # 置換が必要かどうか判断
        cng = memo[i - 1][j - 1] if s1[j - 1] == s2[i - 1] else memo[i - 1][j - 1] + 1
        # 3種類の操作のうち最適のものを求める
        memo[i][j] = min(cng, memo[i][j - 1] + 1, memo[i - 1][j] + 1)
# 解答の出力
print(memo[len(s2)][len(s1)])

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
def edit_dist(s, t):
    INF = float('inf')
    th = INF
    m, n = len(s), len(t)
    if abs(m - n) >= th:
        return INF
    dp = [[INF] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1): dp[i][0] = i
    for j in range(n + 1): dp[0][j] = j
    for i in range(m):
        for j in range(n):
            dp[i + 1][j + 1] = min(dp[i][j] + (s[i] != t[j]), dp[i][j + 1] + 1, dp[i + 1][j] + 1)
    return dp[m][n]

print(edit_dist(input(), input()))