Leetcode 72) Edit Distance

19 Aug 2021 in Algorithms

내 답안

• DP를 붙잡고 씨름한지 몇주째… 드디어 감이 좀 온거같다..! 생각하지 말고 공식에 따르면 풀림… 내머리로 알고리즘을 짜내서 풀 수 있는 그런게 아녔당…

class Solution {
    int[][] dp;
    public int minDistance(String word1, String word2){
        //가장 긴 subsequence를 찾는 문제랑 비슷해지지 않을까?
        dp = new int[word1.length()+1][word2.length()+1];
        for(int[] ddp : dp){
            Arrays.fill(ddp,-1);
        }
        return lcs(word1,word2);        
    }
    public int lcs(String w1, String w2){
        int l1 = w1.length();
        int l2 = w2.length();
        if(l1==0 && l2==0){
            return 0;
        }else if(l2==0){
            return l1;
        }else if(l1==0){
            return l2;
        }

        if(dp[w1.length()][w2.length()]!=-1){
            return dp[w1.length()][w2.length()];
        }


        if(w1.charAt(l1-1) == w2.charAt(l2-1)){
            return lcs(w1.substring(0,l1-1),w2.substring(0,l2-1));
        }else{
            //add, replace, delete중에 고르기
            //replace, delete,add
            int res= 1+Math.min(Math.min(lcs(w1.substring(0,l1-1),w2.substring(0,l2-1)),lcs(w1.substring(0,l1-1),w2)),1+lcs(w1,w2.substring(0,l2-1)));
            return res;
        }

    }
}

다른 답안

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 = 0; i <= len1; i++) {
            dp[i][0] = i;
        }
        for (int j = 0; j <= len2; j++) {
            dp[0][j] = j;
        }

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

        return dp[len1][len2];
    }
}