Menu

Subscribe

[JAVA/LeetCode] Top 100 Liked Question: 72. Edit Distance

HEESOO on Leetcode

👀 문제

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

👊 도전

1. 설계

  1. DP를 이용한다.

2. 구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

/**
 *
 * @author HEESOO
 *
 */
class Solution {
    public int minDistance(String word1, String word2) {
        int m=word1.length();
        int n=word2.length();
        int[][] dp=new int[m+1][n+1];
        for(int i=0;i<=m;i++) dp[i][0]=i; // 초기화
        for(int j=0;j<=n;j++) dp[0][j]=j;
        
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                // i, j 문자가 같으면 변경 필요 없음
                if(word1.charAt(i-1)==word2.charAt(j-1)) dp[i][j]=dp[i-1][j-1];
                else{ // 다른 경우
                    int insert=dp[i][j-1];
                    int delete=dp[i-1][j];
                    int replace=dp[i-1][j-1];
                    dp[i][j]=Math.min(insert, Math.min(delete, replace))+1; // 셋 중 가장 작은 값+1(이번에 수행한 것)  
                }
            }
        }
        
        return dp[m][n];
    }
}

3. 결과

실행결과 🤟 성공 🤟

4. 설명

  1. DP를 이용한다
    • word1는 i, word2는 j로 문자를 체크한다.
    • dp[i][j]: word1의 i번째, word2의 j번째를 바꿀 때, 최소 횟수(이전까지의 횟수에 누적)
    • i, j는 1부터 시작한다. 따라서 charAt()을 쓸 때는 -1해야한다.
    • 빈 문자열과 word를 비교할 수도 있으므로 m+1, n+1로 배열을 선언하여 0~m 또는 n까지 체크할 수 있게 하였다.
    • i==0 또는 j==0인 곳은 해당 word와 빈 문자열을 비교하는 것과 같다. 따라서 내 word와 같게 계속 삽입하면 되므로 그 횟수로 초기화한다.
    • i와 j를 변경하는 세 가지 방법 insert, delete, replace 중, 처음부터 현재 i, j까지를 고려했을 때, 가장 적은 횟수가 드는 것을 선택하고, 여기에 지금 수행한 것(셋 중 하나)를 +1한다.
    • insert: i 자리에 알파벳을 추가하므로, j는 i+1에서 체크한다. 다시말하면 j-1과 i를 체크하는 것과 같으므로 dp[i][j-1]이다.
    • delete: i를 삭제하는 것이므로 j는 i+1와 비교한다. 즉, j-1과 i를 비교하는 것과 같으므로 dp[i][j-1].
    • replace: i를 j로 바꾸는 것이므로 이전의 i-1, j-1을 그대로 가져오면 된다. dp[i-1][j-1].
    • 셋 중 가장 작은 값을 Math.min()을 두 번 사용함으로써 뽑고, 여기에 현재 수행한 횟수 1을 더한다.
    • 마지막 dp[m][n]에 최종으로 min 값이 들어있다.

👏 해결 완료!