72. Edit Distance (classic. DP problem)

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.

You have the following three operations permitted on a word:

• Insert a character
• Delete a character
• Replace a character

Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation: 
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')

 

한줄요약

horse -> ros 와 단어 similarity는 ? (몇번 바꿔야 되나? ) 

 

추가설명 :

edit distance 는 두단어의 dissimilar의 정도를 측정하는데, 스펠링 틀렸을때 추천단어를 기입해준다거나 등 eal world에서도 사용되는 알고리즘이다. 

 

아이디어 생각 방식 : 

dp 가 그렇듯, 위의 문제도 문제에서 문제가 어떻게 소분 될 수 있는지 설명이 되어있다.

각 단계에서는 삽입, 삭제, 교체 3개의 액션을 취할 수 있다. 이전까지의 작업이 최솟값으로 구성되어 왔었다면,

현재 단계에서는 3개의 액션중 1개를 선택하여 (+1) 대응 되는 단어를 만들어 내야한다. 

 

 

    0  r   o  s

   [0, 1, 2, 3],

h [1, 1, 2, 3],

o [2, 2, 1, 2],

r [3, 2, 2, 2],

s [4, 3, 3, 2],

e [5, 4, 4, 3]

 

위 케이스에서

r -> h 가 되기위해 1번 교체 해야한다. 

r -> h, o 가 되기위해 1번 교체 후 1번 더해야한다.

r -> h, o , r 가 되기위해 1번 교체 후 1+1번 더해야한다. 

r -> h, o, r, s 가 되기위해 1번 교체후 2+1번 더해야한다 .

위처럼 다음 목표는 이전 최솟값 +1 을 수행한다. 

 

이에 따른 코드는 아래와 같다.

 

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m = len(word1)
        n = len(word2)
        # dp[i][j] := min # Of operations to convert word1[0..i) to word2[0..j)
        dp = [[0] * (n + 1) for _ in range(m + 1)] ## 2차원 배열 생성 

        dp[0][0]=0
        for i in range(1,m+1): ## 0에서 horse 를 생성하기 위해선 1글자씩 더하면 되고,
            dp[i][0]=i         ## 이에 따라 그냥 1씩 늘리면 된다. 
        for i in range(1,n+1):
            dp[0][i]=i

        for i in range(1,m+1):
            for j in range(1,n+1): ##word2
                if word1[i-1]==word2[j-1]:  ## word1[i-1]번째와 word2[j-1]번째 글자가 같으면 
                        					## 아무 처리를 할 필요가 없고, 뺀것과 같다. 
 											## 따라서 좌측상단 값을 가져온다.
                                            ## 상단->하단: 추가  
                                            ## 좌측->우측: 추가
                    #print("w1, w2 : ", word1[i-1],word2[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)
        #print("dp:",dp[m][n])
        return dp[m][n]