[Java] Daily LeetCode Challenge 72. Edit Distance ★

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

Edit Distance - LeetCode

 

DP 사용해서 문제인데, 사실 너무 감이 오지 않아서 여러 검색을 통해 푸는 방법을 알아보았다.

지금까지 풀어본 몇 안 되는 Hard 유형 중에서 가장 어려웠던 문제.. 유튜브 설명을 보고 공부했다.

다음에 또 다시 풀어봐야함!

 

유튜브 참조 : https://www.youtube.com/watch?v=b6AGUjqIPsA 

 

 

[코드]

class Solution {
    public int minDistance(String word1, String word2) {
        int len1 = word1.length(), len2 = word2.length();

        int[][] dp = new int[len1+1][len2+1];

        for(int i=1; i <= len1; i++)
            dp[i][0] = i;

        for(int i=1; i<= len2; i++)
            dp[0][i] = i;

        for(int i=1; i <= len1; i++){
            for(int j=1; j <= len2; j++){
                if(word1.charAt(i-1)==word2.charAt(j-1))
                    dp[i][j] = dp[i-1][j-1];
                else   // (대체, 삽입, 제거 => 비용 1)  +  (가장 최솟값)
                    dp[i][j] = 1 + Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1]));
            }
        }

        return dp[len1][len2];
    }
}