[JS] Edit Distance

🔒 문제 (LeetCode 72)

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

Constraints:

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

 

🌊 입출력

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

 

---

 

🔑 해결

🌌 알고리즘 - DP

dp[i][j] = word[:i]를 word[:j]로 바꾸는 데 필요한 step의 최소값을 저장한다.

f(i, j) 가 word[:i]를 word[:j]로 바꾸는 데 필요한 step의 최소값을 구하는 함수라고 하면

1) word[i] === word[j] 인 경우 

문자 변경이 필요 없으므로

f(i, j) = f(i - 1, j - 1)

2) word[i] !== word[j] 인 경우

insert, delete, replace 중 하나가 수행되어야 하고, 그중 step을 최소화하는 경우를 택한다.

f(i, j) = 1 + min { f(i, j - 1), f(i - 1, j), f(i - 1, j - 1) }

• f(i, j - 1), : insert
• f(i - 1, j) : delete
• f(i - 1, j - 1) : replace

 

/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
var minDistance = function(word1, word2) {
    const [m ,n] = [word1.length, word2.length]
    const dp = new Array(m+1).fill().map(() => new Array(n+1))
    for(let i = 0; i <= m; i++) {
        dp[i][0] = i
    }
    for(let i = 0; i <= n; i++) {
        dp[0][i] = i
    }
    
    for(let i = 0; i < m; i++) {
        for(let j = 0; j < n; j++) {
            if(word1[i] === word2[j]) {
                dp[i+1][j+1] = dp[i][j]
            } else {
                const [inserted, deleted, replaced] = [dp[i+1][j], dp[i][j+1], dp[i][j]]
                dp[i+1][j+1] = Math.min(Math.min(inserted, deleted), replaced) + 1
            }
        }
    }
    
    return dp[m][n]
};