LeetCode Edit Distance (JavaScript), DP

링크 : https://leetcode.com/problems/edit-distance/description/

문제 설명

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

Example 1:

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

Example 2:

Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation:
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')

Constraints:

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

---

문제 풀이

접근 방식 (DP를 이용해 풀이)

1. word1, word2의 길이 + 1 만큼의 2차원 배열을 생성 (""인 경우도 고려해 + 1한 값을 배열로 생성)
2. i번째 (word1기준) 까지의 부분 문자열로 j번째 (word2기준) 까지 부분 문자열로 만들 수 있는 경우의 수 구하기
   • (i, j) = word1의 i 번째까지로 word2의 j 번째까지 만드는 최소의 경우의 수를 의미
   • dp[i - 1][j] : Delete, 삭제
     • word1의 i - 1번째까지가 j 번째와 같다면 i번째는 쓸모없으니 제거해야함
   • dp[i - 1][j - 1] : Replace, 교체
     • word1의 i - 1번째가 word2의 j - 1번째와 같을 때 다음 문자는 word2에 맞게 교체되어야 함
   • dp[i][j - 1] : Insert, 삽입
     • word1의 i번째까지가 word2의 j - 1번째까지와 같다면 word2의 j번째 문자를 추가해야함

(i, j)	""	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

 

[ 좀 더 자세한 설명, (1, 1)에서 최소 비용 구하는 과정 ]

 

결국 (i, j)를 구하는 방식은 다음과 같이 이해할 수 있다.

( i - 1, j - 1 ) 교체	( i - 1, j ) 삭제
( i, j - 1 ) 삽입	( i, j ) 현재 위치

따라서, 현재 위치는 교체된 값, 삭제된 값, 삽입된 값에 + 1(현재 j번째의 word2 문자를 더하기)을 한 값 중에서 최소 값을 구하면 된다.

 

만약 위 같은 표가 왜 저렇게 나오는지 이해가 되지않는다면, 먼저 삽입, 삭제, 교체가 어떠한 기준으로 이루어지는지 글로 먼저 이해를 하고 이를 표로 정리해보는게 좋을 것 같다.

e.g. 삽입의 경우 글로 이해를 해본다면, word1의 i 위치까지의 부분 문자열과 word2의 j 위치까지의 부분 문자열이 같아야 하고, word2의 j가 추가가 되어야 한다면, word1은 i번째가 아닌 i - 1번째에 j를 추가해야 된다.

/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
var minDistance = function(word1, word2) {
    const [rows, cols] = [word1.length, word2.length];
    const dp = Array.from({length: rows + 1}, () => Array.from({length: cols + 1}, () => 0));

    for (let i = 0; i <= rows; i++) {
        dp[i][0] = i;
    }
    for (let j = 0; j <= cols; j++) {
        dp[0][j] = j;
    }

    for (let i = 1; i <= rows; i++) {
        for (let j = 1; j <= cols; j++) {
            // 비교하는 두 문자가 같다면 대각선 위 (변경 x)
            if (word1[i - 1] === word2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = Math.min(
                    dp[i - 1][j], // 삭제
                    dp[i - 1][j - 1], // 교체
                    dp[i][j - 1] // 삽입
                ) + 1;
            }
        }
    }

    return dp[rows][cols];
};

---

결론

bfs와 같은 형태로 문제를 해결할 순 있지만, 문자의 길이가 길어지면 시간 오류가 발생하게 된다.

따라서, DP와 같은 알고리즘으로 접근을 해서 해결을 해야한다.

 

위 문제도 DP를 이용해 접근을 해야 하지만, 문제를 이해하는 과정이 생각보다 쉽지 않다고 느껴졌다.

왜 2차원 배열의 특정 위치가 삽입, 삭제, 교체가 되는지 이해를 하는게 이 문제를 해결할 수 있는 방법인 것 같다.

 

만약 위 설명들로도 이해가 잘 가지 않는다면 아래 영상을 참고하면 이해가 될 수 있을 것 같다.

https://www.youtube.com/watch?v=6jvSfC2-JDo