A Variation of LC No.72 Edit Distance


  • 0
    J

    It is just a variation of problem No.72 Edit Distance, with slightly different transition calculation.

    In the problem Edit Distance, we have three operations:

    1. insert a character
    2. delete a character
    3. replace a character

    "insert" and "delete" are essentially the same operation: insert to string A is same as delete from string B; a "replace" operation is a combination of a "insert" and a "delete".

    The difference is that we don't have "replace" operation in this problem, so we just need to remove that transition path. Also the cost become the ASCII value of the deleted character instead of "1".

    class Solution {
        public int minimumDeleteSum(String s1, String s2) {
            int m = s1.length();
            int n = s2.length();
            int[][] dp = new int[m+1][n+1];
            
            for(int i = 1; i < dp[0].length; i++){
                dp[0][i] = dp[0][i-1] + s2.charAt(i-1);
            }
            
            for(int i = 1; i < dp.length; i++){
                dp[i][0] = dp[i-1][0] + s1.charAt(i-1);
            }
            
            for(int i = 0; i < s1.length(); i++){
                for(int j = 0; j < s2.length(); j++){
                    if(s1.charAt(i) == s2.charAt(j)) dp[i+1][j+1] = dp[i][j];
                    else dp[i+1][j+1] = Math.min(dp[i][j+1]+ s1.charAt(i), dp[i+1][j] + s2.charAt(j));
                }
            }
            return dp[m][n];
        }
    }
    

    Attached is the solution to "Edit Distance"

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

Log in to reply
 

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