[LeetCode] 72. Edit Distance, Medium

1. 문제

• 문자열 word1, word2가 주어질 때, word1을 word2로 만들 수 있는 최소 연산 횟수를 구하라.
• 연산의 종류는
  • 문자를 추가한다.
  • 문자를 제거한다.
  • 문자를 교체한다.

2. 해결

function minDistance(word1: string, word2: string): number {
    const m = word1.length;
    const n = word2.length;

    // dp 배열 생성 (m+1) x (n+1) 크기
    const dp: number[][] = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));

    // 초기 상태 설정
    for (let i = 0; i <= m; i++) {
        dp[i][0] = i; // word1의 첫 i글자를 삭제하는데 i번 연산이 필요
    }

    for (let j = 0; j <= n; j++) {
        dp[0][j] = j; // word2의 첫 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 {
                dp[i][j] = Math.min(
                    dp[i - 1][j] + 1,  // 삭제
                    dp[i][j - 1] + 1,  // 삽입
                    dp[i - 1][j - 1] + 1  // 대체
                );
            }
        }
    }

    // 결과 반환
    return dp[m][n];
}

• 일단 못풀었다. 두 문자열로 2차원 배열을 만들어서 누적해 나가는 것 까진 알겠는데, 그것만 보고 어떻게 삽입 삭제 대체 연산 횟수를 구분하는가 알 수 없었다.
• 두 문자열의 길이 +1만큼 2차원 배열을 생성한다. 그 이유는 word1과 word2가 빈 문자열인 경우부터 시작해야 쌓아 나갈 수 있다.

	""	r	o	s	e
""	0	1	2	3	4
h	1	1	2	3	4
o	2	2	1	2	3
r	3	3	2	2	3
s	4	4	3	2	3
e	5	5	4	3	3

• 먼저, 0번 행을 보면 빈 문자열을 차례대로 "", r, ro, ros, rose 문자열로 만드는 방법은 삽입만 해주면된다.
• 0번 열은 차례대로 "", h, ho, hor, hors, horse를 빈문자열로 만드는 방법은 삭제만 해주면 된다.
• 다음 h -> r로 바꿔야 하는 1, 1부터 채워나간다 이 때, 연산을 고려해야 하는데 아래와 같다.
  • 삭제: h를 r로 만들려고 삭제를 한다 (연산 1번), 이러면 빈 문자열이 되는데 h->r로 바꿔야 하는 상태가 "" -> r로 바꿔야 하게 됐다. 이는 dp[0][1] (빈 문자열에서 삽입하여 r로 만드는 방법의 수)가 되므로 dp[0][1] + 1로 2가 된다.
  • 삽입: h를 r로 만들려고 삽입을 한다 (연산 1번), 이러면 hr이 되는데 h->r로 바꿔야 하는 상태가 hr -> r로 바꿔야 하는 상태가 됐다. 이는 dp[1][0] (h를 빈문자열로 만드는 방법의 수)가 되므로 dp[1][0] + 1로 2가 된다.
  • 대체: h를 r로 만들기 위해서 교체한다. 이는 이전 까지의 문자까지 쌓아온 같아지는 방법의 수 +1이므로 dp[0][0] +1이 된다.
• 위 같은 방식으로 점화식을 세우면 Math.min(dp[i][j-1] + 1, dp[i-1][j] + 1, dp[i-1][j-1] + 1)로 최소 값을 가져가면 된다.