LeetCode: 72번 (Edit Distance) [JAVA]

문제 링크

https://leetcode.com/problems/edit-distance/

Edit Distance - LeetCode

풀이

전체적인 풀이 과정은 다음과 같다.

1. 주어진 word1의 길이, word2의 길이만큼의 2차원 배열 생성
2. 0번째 열의 행들을 따라, 각 행 순서만큼의 숫자를 insert
3. 0번째 행의 열들을 따라, 각 열 순서만큼의 숫자를 insert
   
4. 이후 이중 for문(i, j)을 통해 word1과 word2 문자열을 바탕으로 2차원 배열 값을 채움
   1) word1[i]와 word2[j]가 같다면, 이차원 배열의 (i, j) 값은 (i-1, j-1)값을 그대로 대입
   2) 둘이 다르다면, (i-1, j), (i, j-1), (i-1, j-1) 값 중 최소값+1을 대입
5. 이차원 배열의 오른쪽 끝 값을 반환

 문제 자체가 생각보다 매우 어려워서 고민했었는데, 이를 해결하는 별도의 알고리즘 자체가 존재했었다. Levenshtein distance(편집 거리 알고리즘)이라고 불리는 알고리즘을 사용하면 이를 쉽게 해결할 수 있다.
 결국 핵심은 일종의 점화식인데, 문자열 A와 B를 비교할 때 한 번에 모든 문자를 비교하려는 것이 아닌, A와 B를 부분 문자열로 쪼갠 후 비교해 나가는 방법이다. A와 B의 부분 문자열 a와 b에 대해 최소 문자 변경 횟수를 찾기 위해 크게 세 가지를 고려하게 되는데, 바로 a에서 마지막 문자를 뺀 a`와 b에서 마지막 문자를 뺀 b`, a와 b`, a`와 b, 이렇게 세 가지 쌍의 경우의 수를 고려한다. 앞선 세가지 경우의 수에 대해 최소 변경 횟수가 답이 구해져있다면, 이들을 바탕으로 a와 b의 최소 변경횟수는 다음과 같이 찾을 수 있다.
 우선 (a`, b)를 가지고 (a, b)의 답을 찾는 방법은, 결국 a` -> b를 만드는 최소 횟수에서 a` 마지막에 추가로 붙게 되는 문자를 삭제하는 경우의 수만 추가해주면 된다. 그리고 (a, b`)를 가지고 (a, b)의 답을 찾는 방법은 a -> b`를 만드는 최소 횟수에서 b` 마지막에 추가로 붙게 되는 문자를 나중에 추가해주는 경우의 수만 추가해주면 된다. 마지막으로 (a`, b`)를 가지고 (a, b)의 답을 찾는 방법은, a` -> b`를 만드는 최소 횟수에서 a`와 b` 마지막에 추가로 붙은 문자를 수정해주는 경우의 수만 추가해주면 된다. 물론 약간의 예외 케이스가 존재하는데, 만약 양쪽에 추가된 문자가 동일하다면, 이를 수정해주는 경우의 수를 추가할 필요가 없다.
 앞선 개념을 바탕으로 문제를 풀기 위해선 우선 이차원 배열을 생성한다. dynamic programming을 위해 주어진 word1과 word2의 길이+1 (길이 0부터 커버하기 위해)만큼의 이차원 배열 dp를 생성해준다. 그리고 우선 0번째 열의 행들을 따라 각 행의 순서만큼의 숫자를 insert 해주고, 0번째 행의 열들을 따라 각 열 순서만큼의 숫자를 insert해주는데, 이는 단순히 반대 문자열이 ""일 때 해당 문자열이 그만큼 문자를 삭제, 삽입 해줘야 하기 때문이다.
 이후에는 단순히 앞선 개념을 바탕으로 답을 채워나가면 된다. 이중 for문(i, j)을 통해 문자열 word1과 word2의 특정 인덱스의 문자를 비교해나가며, 둘의 문자가 같다면 단순히 dp[i][j] = dp[i-1][j-1]을 해주고, 둘이 다르다면 dp[i-1][j], dp[i][j-1], dp[i-1][j-1] 중 최소값을 가져와 1을 더한 값을 저장해주면 된다. 마지막으로는 dp[word1.length()][word2.length()]의 값을 반환해주면 된다.

 

class Solution {
    public int minDistance(String word1, String word2) {
        if (word2.length() == 0) {
            return word1.length();
        }

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

        for (int i = 1; i <= word1.length(); i++) {
            dp[i][0] = i;
        }

        for (int i = 1; i <= word2.length(); i++) {
            dp[0][i] = i;
        }

        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(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                }
            }
        }

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

결과