[LeetCode] Edit Distance

https://leetcode.com/problems/edit-distance/description/?envType=study-plan-v2&envId=leetcode-75

 

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.

---

두 개의 문자열 word1과 word2가 주어지고,

word1이 word2와 똑같아질 때까지 문자를 추가/삭제/수정하는 가장 적은 횟수를 구한다.

 

/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
var minDistance = function(word1, word2) {
    // word1을 word2로 바꾸기 위한 최소 횟수
    // 바꿀건지 삭제할건지 추가할건지 결정해야 한다.
    const m = word1.length;
    const n = word2.length;
    // dp[i][j] = word1의 앞 i개의 글자 & word2의 앞 j개의 글자의 minDistance
    const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));

    for(let i=1; i<m+1; i++) dp[i][0] = i; // 초기값 -> i만큼 전체삭제
    for(let j=1; j<n+1; j++) dp[0][j] = j; // 초기값 -> j만큼 삽입

    for(let i=1; i<m+1; i++){
        for(let j=1; j<n+1; j++){
            if(word1[i-1] == word2[j-1]){
                // 현재 글자가 같으면 유지
                dp[i][j] = dp[i-1][j-1];
            }else{
                // 바꾸는 경우
                // 삭제할건지(dp[i-1][j]), 삽입할건지(dp[i][j-1]), 교체할건지(dp[i-1][j-1])
                // 그 중에 가장 작은 값 + 1
                dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1;
            }
        }
    }
    return dp[m][n];
};

 

이것도 DP 문제다.

아무튼.

 

horse, ros이고, m=4, n=3이라고 했을 때.

dp[4][3] 은 hors를 ros로 만들기 위한 최소 숫자를 의미한다.

 

모든 경우의 전제조건은,

dp[i][j]는 word1의 i번째까지의 문자열이 word2의 j번째까지의 문자열이 되기 위한 최소 횟수라는 점이다.

 

1. 삭제하는 경우에는 dp[i-1][j] + 1

word1의 i번째자리 글자를 삭제하는 경우의 최소 횟수를 나타낸다.

dp[3][3], hor를 ros로 바꾸는 최소 횟수에 1을 더하면 hors가 ros로 변경되는 횟수가 된다.

hors의 i번째(=4) 글자 s를 삭제하는 동작 1이 더해지는 셈이므로!

 

2. 삽입하는 경우에는 dp[i][j-1] + 1

이 테스트케이스의 경우에는 굳이 글자를 더할 필요가 없어서 직관적이지는 않지만...

word2의 j번째 글자를 삽입하는 경우를 가정하고 있으므로,

word1의 i번째, word2의 j-1번째까지의 문자열을 비교한 값에 1을 더한다.

word1의 i번째, word2의 j-1번째까지의 최소횟수에 word2의 j번째 글자를 더하는 동작을 1회 더하는 것이다.

 

3. 교체하는 경우에는 dp[i-1][j-1] + 1

dp[3][2], hor를 ro로 바꾸는 최소 횟수에 1을 더한다.

word1의 i번째 글자를 word2의 j번째 글자로 교체하는 동작 1회를 의미한다.

 

 

DP 문제들은 참 비슷비슷하면서도 언제나 다르게 느껴지는 것 같다...