LeetCode 72(Edit Distance, Python)

1. 문제 링크

• https://leetcode.com/problems/edit-distance/

LeetCode - The World's Leading Online Programming Learning Platform

2. 문제 설명

• 두 개의 문자열(word1과 word2)이 주어졌을 때, 한 문자열을 다른 문자열로 변환하기 위해 필요한 최소 편집 연산의 수를 찾는 문제
• 가능한 연산은 세 가지로
  • 삽입(Insert): 한 문자를 삽입
  • 삭제(Delete): 한 문자를 삭제
  • 교체(Replace): 한 문자를 다른 문자로 교체
• 예시) "horse"를 "ros"로 변환하기 위해 필요한 최소 편집 연산 아래와 같으므로 3임.
  1. horse -> rorse ('h' 를 'r'로 교체)
  2. rorse -> rose (’r’ 삭제)
  3. rose -> ros (’e’ 삭제)

3. 처음 풀이

• 스스로 풀지 못하고 끝내 다른 사람의 풀이를 보았음. 충격적이었다!
• 1월 19일에 업로드되었어야 할 글인데 풀지를 못해서 이제 업로드. 
• 아직 DP를 활용하는 것에 익숙하지 못하여 연습이 필요함. 
• DP를 떠올리질 못했다. 

4. 다른 풀이

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

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

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

    for i in range(1, m + 1):
      for j in range(1, n + 1):
        if 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

    return dp[m][n]

5. 배운 점(풀이의 설명)

• 레벤슈타인 거리(levenshtein distance), 편집 거리(edit distance)라고 불리는 문제.
• DP을 이용한 알고리즘으로 해결
• 문장의 유사도를 나타낸다. 유전자의 유사도 분석에도 사용된다. 
• 예시로 주어진 "horse"를 "ros"로 변환하기 위해 필요한 최소 편집 연산을 구해보자.
• “horse”의 부분 문자열인 “”, “h”, “ho”, “hor”, “hors”, “horse” 각각을 “ros”의 부분 문자열인 “”, “r”, “ro”, “ros”로 바꾸는데 필요한 최소 편집 연산으로 단계별로 생각하자.
• “”를 “”, “r”, “ro”, “ros”로 바꾸는데 필요한 최소 편집 연산 수는 당연히 0, 1, 2, 3이다.
• “h”를 “”, “r”, “ro”, “ros”로 바꾸는데 필요한 최소 편집 연산 수는 1, 1, 2, 3이다.
• “ho”를 “”, “r”, “ro”, “ros”로 바꾸는 데 필요한 최소 편집 연산 수는 2, 2, 1, 2이다.
  • 여기서 “o”가 일치하여 특이점 1이 생김. 이 경우 “o”를 제외하고 “h”를 “r”로 바꾸는 경우(행렬의 왼쪽 위 대각선)의 값과 같다.
  • 특이점 1로 인해 그 오른쪽 값이 2가 되었음. “ro”로 바꾸는데 1이 필요하니까 “ros”로 바꾸는 데는 2가 필요하다. “s”를 추가하기 때문. 오른쪽으로 가며 +1 하는 것은 한 글자 추가하는 것이다. 반대로 위에서 아래로 가며 +1하는 것은 한 글자 삭제. 오른쪽 아래 대각선으로 가며 +1 하는 것은 한 글자 수정임을 알 수 있다.
  • 즉, 추가되는 글자가 두 문자열에서 같으면 대각선 값을 그대로 가져온다. 그렇지 않다면 삽입(왼쪽 값), 삭제(위쪽 값), 교체(대각선 값)에 +1을 하면 되므로 세 개의 값 중 가장 작은 값에 +1한 값을 쓰면 된다.
• “hor”를 “”, “r”, “ro”, “ros”로 바꾸는 데 필요한 최소 편집 연산 수는 3, 2, 2, 2이다.
  • r 같으므로 2/o, r은 다르므로 최솟값(위쪽 값) 1에 +1하여 2/s, r 다르므로 최솟값(대각선 값) 1에 +1하여 2
• “hors”를 “”, “r”, “ro”, “ros”로 바꾸는 데 필요한 최소 편집 연산 수는 4, 3, 3, 2이다.
• “horse”를 “”, “r”, “ro”, “ros”로 바꾸는 데 필요한 최소 편집 연산 수는 5, 4, 4, 3이다.
• 따라서 결과적으로 “horse”를 “ros”로 바꾸는데 필요한 최소 편집 연산 수는 3이다.