Standard dp solution


  • 22
    S
    int minDistance(string word1, string word2) {
        int  m = word1.length(), n = word2.length();
        if (m == 0) return n;
        if (n == 0) return m;
        
        // table[i][j]: distance from words1.substr(0, i) to words2.substr(0, j) 
        int table[m+1][n+1];
        for (int i = 0; i <= m; ++i) table[i][0] = i;
        for (int j = 0; j <= n; ++j) table[0][j] = j;
        // table[i][j] is the min distance between the next three values
        // from table[i-1][j], table[i][j-1], or table[i-1][j-1] to table[i][j]
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                int cost = (word1[i-1] == word2[j-1] ? 0 : 1);
                table[i][j] = min(min(table[i-1][j] + 1, table[i][j-1] + 1), table[i-1][j-1] + cost);
            }
        }
        
        return table[m][n];
    }

  • 4
    D

    Below is my same code in Java

    public class Solution {
        public int minDistance(String word1, String word2) {
            if(word1.length() == 0) return word2.length();
            if(word2.length() == 0) return word1.length();
            
            int[][] ed = new int[word1.length()+1][word2.length()+1];
            for(int i = 0; i<word2.length(); i++){
                ed[word1.length()][i] = word2.length() - i; 
            }
            for(int j = 0; j<word1.length(); j++){
                ed[j][word2.length()] = word1.length()-j;
            }
            for(int i = word1.length()-1; i>=0; i--){
                for(int j = word2.length()-1; j>=0; j--){
                    if(word1.charAt(i) == word2.charAt(j)){
                        ed[i][j] = ed[i+1][j+1];
                    }else{
                        ed[i][j] =1+ Math.min(ed[i+1][j+1], Math.min(ed[i+1][j], ed[i][j+1]));
                    }
                }
            }
            return ed[0][0];
        }
    }

  • 0
    S

    it think you can make it more clean


  • 0
    L

    when thinking in dp we have to go from end to front. when implementing using table we have to go from front to end.


  • 0
    N

    Dijkstra's Algorithm is DP.


  • 0
    K
    public class Solution {
        public int minDistance(String word1, String word2) {
            int[][] dp = new int[word1.length()+1][word2.length()+1];
            for(int i = 0; i < dp.length; i++) {
                for(int j = 0; j < dp[0].length; j++) {
                    if(i == 0) dp[i][j] = j;
                    else if(j == 0) dp[i][j] = i;
                    else {
                        int cost = word1.charAt(i-1) == word2.charAt(j-1) ? 0 : 1;
                        dp[i][j] = Math.min(dp[i-1][j-1]+cost,Math.min(dp[i-1][j]+1,dp[i][j-1]+1));
                    }
                }
            }
            return dp[word1.length()][word2.length()];
        }
    }

Log in to reply
 

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