Edit Distance - LeetCode

Problem

1. input: 문자열 word1, 문자열 word2
2. output: word1을 word2로 만들 수 있는 최소 연산 횟수 리턴
3. 가능한 연산
   • 한글자 삽입
   • 한글자 삭제
   • 한글자 대체

• 0 <= word1.length, word2.length <= 500
• word1 and word2 consist of lowercase English letters.

Idea

최소 편집 거리 알고리즘 문제로 DP(Tabulation)을 통해 쉽게 풀 수 있다.

두 문자열의 부분문자열을 비교하여 쌓아나가면 된다 → Sol1

Solution

1. DP(Tabulation)

   가능한 연산은 3가지

   • 한글자 삭제: dp[i-1][j]
   • 한글자 추가: dp[i][j-1]
   • 한글자 대체: dp[i-1][j-1]

   dp[i][j] → 문자열1[0:i]을 문자열2[0:j]로 변환하기 위해 필요한 연산 횟수

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

   class Solution {
       fun minDistance(word1: String, word2: String): Int {
           val dp = Array(word1.length + 1){ IntArray(word2.length + 1) }
           for (i in 1..word1.length) dp[i][0] = i
           for (i in 1..word2.length) dp[0][i] = i
           for (i_ in word1.indices) {
               for (j_ in word2.indices) {
   								// dp 배열에 맞게 idx 조정
                   val i = i_ + 1
                   val j = j_ + 1
                   if (word1[i_] == word2[j_]) { // 비교할 글자가 같은 경우
                       dp[i][j] = dp[i-1][j-1] // 왼쪽 위의 값 그대로 (둘다 한글자 없는 경우와 동일)
                   } else {
   										// 상(한글자 제거), 좌(한글자 추가), 대각선(한글자 대체) 중 최솟값 + 1
                       dp[i][j] = minOf(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
                   }
               }
           }
           return dp[word1.length][word2.length]
       }
   }
   

   시간 복잡도: 문자열 순회 X 문자열 순회 = n^2

   

Point

1. 최소 편집 거리 문제