[LeetCode] 72. Edit Distance

https://leetcode.com/

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.

Code:

var minDistance = function(word1, word2) {
    const m = word1.length;
    const n = word2.length;
    // dp[i][j]는 word1의 첫 i개 문자를 word2의 첫 j개 문자로 만들기 위한 최소 편집 거리
    const dp = Array.from(Array(m + 1), () => Array(n + 1).fill(0));
    // 초기값 설정
    for (let i = 0; i <= m; i++) {
        dp[i][0] = i;
    }
    for (let j = 0; j <= n; j++) {
        dp[0][j] = j;
    }
    // 다이나믹 프로그래밍을 사용하여 최소 편집 거리 계산
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            // 현재 문자가 같으면 이전까지의 최소 편집 거리를 그대로 사용
            if (word1[i - 1] === word2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                // 다르면 이전까지의 최소 편집 거리에서 1을 더하고, 세 연산 중 최솟값 선택
                dp[i][j] = 1 + Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]);
            }
        }
    }
    // 최종 최소 편집 거리 반환
    return dp[m][n];
}

 

Solutions Code:

var minDistance = function(word1, word2) {
    // 최소 편집 거리를 저장할 2차원 배열 dp를 생성합니다.
    let dp = Array(word1.length + 1).fill(null).map(() => Array(word2.length + 1).fill(0));
    // dp 배열의 첫 번째 행과 열을 빈 문자열로부터의 거리로 초기화합니다.
    for (let i = 0; i < dp.length; i++) {
        dp[i][0] = i;
    }
    for (let i = 0; i < dp[0].length; i++) {
        dp[0][i] = i;
    }
    // 동적 계획법을 사용하여 dp 배열을 채웁니다.
    for (let i = 1; i < dp.length; i++) {
        for (let j = 1; j < dp[0].length; j++) {
            // 세 가지 작업의 최솟값을 계산합니다: 삽입, 삭제, 또는 교체
            dp[i][j] = Math.min(
                dp[i - 1][j] + 1,      // 삽입 작업 (왼쪽)
                dp[i][j - 1] + 1,      // 삭제 작업 (위쪽)
                dp[i - 1][j - 1] + (word1[i - 1] !== word2[j - 1] ? 1 : 0)  // 교체 작업 (대각선)
            );
        }
    }
    // 최소 편집 거리는 dp 배열의 오른쪽 하단 셀에 저장됩니다.
    return dp[dp.length - 1][dp[0].length - 1];
}

 

출처 : https://leetcode.com/problemset/all/

Problems - LeetCode