[Java] LeetCode 72: Edit Distance

[문제 바로 가기] - Edit Distance

문제 해석

두 단어 word1과 word2가 주어질 때, word1을 word2로 바꾸기 위해서 필요한 최소한의 횟수를 구해라.

변경 작업에는 1. 문자 삽입 2. 문자 삭제 3. 문자 바꾸기가 가능하다.

---

Dynamic Programming을 이용하여 풀이하면 되는데, 최근 LCS 문제를 풀어서 그런지 LCS 풀이밖에 생각나지 않았다. 비슷한 유형의 문제는 풀이할 수 있는데 아는 부분에서 조금만 변형이 돼도 감을 못 잡는 것 같다.

💡 아이디어

이 문제에서 dp 배열은 변경해야 하는 횟수를 저장하는 용도다.

	int[][] dp = new int[word1.length() + ][word2.length()];

예제의 horse와 ros를 예로 들어보면, 먼저 아래와 같이 word1이나 word2가 빈 문자열일 경우를 채워줘야 한다.

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

이유는 word1이 빈 문자열이라면 word2의 길이만큼 문자를 추가해야 하고, word2가 빈 문자열이라면 word1에서 문자를 삭제해야 하기 때문이다.

	for (int i = 0; i <= word1.length(); i++) dp[i][0] = i;
	for (int j = 0; j <= word2.length(); j++) dp[0][j] = j;

1. 문자가 같다면 변경 횟수 유지
2. 문자가 다르다면 삽입, 삭제, 바꾸기 중 (가장 작은 값 + 1)

word1.charAt(i - 1) = h
word2.charAt(j - 1) = r

위와 같다면, 삭제와 삽입, 바꾸기는 다음과 같다.

• 삭제 : dp[i - 1][j] + 1

word1의 (i - 1)번째 문자를 삭제하는 것이므로 word1은 다음 문자를 탐색해야 하고 word2는 같은 문자를 탐색해야 하기 때문에 dp[i - 1][j]가 된다.

• 삽입 : dp[i][j - 1] + 1

word1에 word2의 문자를 추가하면 rh가 된다. 즉, r을 맞춘 것이기 때문에 word1은 같은 문자를 탐색해야 하고 word2는 다음 문자를 탐색해야 하기 때문에 dp[i][j - 1]가 된다.

• 바꾸기 : dp[i - 1][j - 1] + 1

word1의 h를 word2의 r로 맞춘 것이므로 word1와 word2 모두 다음 문자를 탐색하면 된다.

---

풀이

/**
 * 리트코드 72번 Edit Distance
 * - DP
 */

class Solution {
    public int minDistance(String word1, String word2) {
        int[][] dp = new int[word1.length() + 1][word2.length() + 1];

        for (int i = 0; i <= word1.length(); i++) dp[i][0] = i;
        for (int j = 0; j <= word2.length(); j++) dp[0][j] = j;

        for (int i = 1; i <= word1.length(); i++) {
            for (int j = 1; j <= word2.length(); j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
                }
            }
        }

        return dp[word1.length()][word2.length()];
    }
}