DP solution: based on Edit Distance


  • 0
    Y

    I saw some good solutions based on longest common subsequence. And I'd like to share mine based on EditDistance.

    The only difference is: when word1.charAt(i-1) != word2.charAt(j-1),we couldn't do the "replacement" but have to delete both,which leads to 2 operations.

    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++){
                for(int j = 0;j <= n;j++){
                    if(i == 0&&j == 0){
                        dp[i][j] = 0;
                    }
                    else if(i == 0){
                        dp[0][j] = j;
                    }
                    else if(j == 0){
                        dp[i][0] = i;
                    }
                    else{
                        int last = dp[i-1][j-1];
                        if(word1.charAt(i-1) != word2.charAt(j-1)){
                            last += 2;
                        }
                        dp[i][j] = Math.min(last,Math.min(dp[i-1][j]+1,dp[i][j-1]+1));
                    }
                }
            }
            return dp[m][n];
    

    Any advice is more than welcome :-)


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.