[JS] Delete Operation for Two Strings

🔒 문제 (LeetCode 583)

Given two strings word1 and word2, return the minimum number of steps required to make word1 and word2 the same.

In one step, you can delete exactly one character in either string.

Constraints:

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

 

🌊 입출력

Example 1:

Input: word1 = "sea", word2 = "eat"
Output: 2
Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".

Example 2:

Input: word1 = "leetcode", word2 = "etco"
Output: 4

 

---

 

🔑 해결

🌌 알고리즘 - DP

두 단어가 같아지기 위해  삭제해야 하는 최소 문자 개수

= 두 문자가 공통으로 가지는 문자열(longest common subsequence)을 찾고 각 단어와 공통 문자열을 제외한 문자 개수 합

따라서 DP를 이용하여 longest common usbsequence를 구하고 총 단어 길이에서 빼준다.

/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
var minDistance = function(word1, word2) {
    if(word1 === word2) return 0
    
    const [m, n] = [word1.length, word2.length]
    let dp = new Array(m+1).fill().map(() => new Array(n+1).fill(0))    // longest common subsequence

    for(let i = 1; i <= m; i++) {
        for(let j = 1; j <= n; j++) {
            if(word1[i-1] !== word2[j-1]) {
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1])
            } else {
                dp[i][j] = dp[i-1][j-1] + 1
            }
        }
    }
    
    return m - dp[m][n] + n - dp[m][n]
};