[dp/Goldman Sachs] 편집 거리

2차원 배열 리스트를 이용해서 문자열이 같을 때와, 다를때로 나누어서 진행하면 된다. 

 

점화식

1. 두 문자가 같은 경우: dp[i][j]=dp[i-1][j-1]

2. 두 문자가 다른 경우: 1+min(dp[i][j-1],dp[i-1][j],dp[i-1][j-1])

dp[i][j-1]: 삽입 

dp[i-1][j]: 삭제 

dp[i-1][j-1]: 교체 

 

def edit_dist(str1,str2):
	n=len(str1)
    m=len(str2)
    
    dp=[[0]*(m+1) for _ in range(n+1)]
    
    for i in range(1,n+1):
    	dp[i][0]=i
    for i in range(1,m+1):
    	dp[0][i]=i
        
    for i in range(1,n+1):
       for j in range(1,m+1):
        	if str1[i-1]==str2[j-1]:
            	dp[i][j]=dp[i-1][j-1]
             else:
            	dp[i][j]=1+min(dp[i][j-1],dp[i-1][j],dp[i-1][j-1])
    return dp[n][m]                
    
str1=input()
str2=input()

print(edit_dist(str1,str2))