Java DP Solution, same as Edit Distance


  • 10
    public class Solution {
        public int minDistance(String word1, String word2) {
            int len1 = word1.length(), len2 = word2.length();
            if (len1 == 0) return len2;
            if (len2 == 0) return len1;
            
            // dp[i][j] stands for distance of first i chars of word1 and first j chars of word2
            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(Math.min(dp[i - 1][j - 1] + 2, dp[i - 1][j] + 1), dp[i][j - 1] + 1);
                }
            }
            
            return dp[len1][len2];
        }
    }
    

  • 3
    F

    @shawngao I wonder whether dp[i-1][j-1]+2 could be ignored ? It seems like dp[i-1][j-1]+2>=max{dp[i-1][j]+1, dp[i][j-1]+1}(although I don't know why), so that dp[i-1][j-1]+2 will never be the smallest one.


  • 0

    said in Java DP Solution, same as Edit Distance:

    else
    dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1] + 2, dp[i - 1][j] + 1), dp[i][j - 1] + 1);

    The only difference part comparing with "Edit Distance". Else are same.

    in Edit Distance is(I start i,j from 0, end (< word1.Length, <word2.Length)

                    else
                    {
                        dp[i+1, j + 1] = 
                        Math.Min(Math.Min(dp[i,j+1],dp[i+1,j]), 
                                dp[i,j]) + 1;
                    }
    

    In here, it's

                    else
                    {
                        dp[i+1, j + 1] = 
                        Math.Min(Math.Min(dp[i,j+1], dp[i,j]+1), 
                                 dp[i+1,j]) +1;
                    }
    

  • 0
    F

  • 8

    0_1495160741303_WechatIMG8.jpeg


  • 0
    M

    Reduce space to O(n). C++ version.

    class Solution {
    public:
        int minDistance(string word1, string word2) {
            size_t m = word1.length(), n = word2.length();
            vector<int>f(n+1,0);
            for(size_t j=0; j<=n; j++) 
                f[j] = j;
            for(size_t i=1; i<=m; i++) {
                int prev = f[0];
                f[0] = i;
                for(size_t j=1; j<=n; j++) {
                    int save = f[j];
                    if(word1[i-1]==word2[j-1]) f[j] = prev;
                    else f[j] = min(prev+2, min(f[j]+1, f[j-1]+1));
                    prev = save;
                }
            }
            return f[n];
        }
    };
    

  • 2

    @shawngao said in Java DP Solution, same as Edit Distance:

    Math.min(Math.min(dp[i - 1][j - 1] + 2, dp[i - 1][j] + 1), dp[i][j - 1] + 1);

    Nice solution. Since we're permitted to operate only one character at a time, checking to delete both characters is not required, although it produces same result since you add 2.
    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + 1;


Log in to reply
 

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