Java O(n) Similar idea of Edit Distance and LC 524


  • 2
    Y

    LC 72 Edit Distance and LC 524 Longest Word through Deleting share the same idea as this one. The difference lies in the "cost" definition, this question defines "cost" as the ASCII sum while the other two as the distance. We just need to simply apply the definition in the program.

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

  • 1
    L

    Thank you for comparing the three problems. good summary!


Log in to reply
 

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