Java DP Solution (Longest Common Subsequence)


  • 32

    To make them identical, just find the longest common subsequence. The rest of the characters have to be deleted from the both the strings, which does not belong to longest common subsequence.

    public int minDistance(String word1, String word2) {
        int dp[][] = new int[word1.length()+1][word2.length()+1];
        for(int i = 0; i <= word1.length(); i++) {
            for(int j = 0; j <= word2.length(); j++) {
                if(i == 0 || j == 0) dp[i][j] = 0;
                else dp[i][j] = (word1.charAt(i-1) == word2.charAt(j-1)) ? dp[i-1][j-1] + 1
                        : Math.max(dp[i-1][j], dp[i][j-1]);
            }
        }
        int val =  dp[word1.length()][word2.length()];
        return word1.length() - val + word2.length() - val;
    }

  • 3
    O

    Nice Observation! This is probably the best way to think about it.


  • 6
    Y

    Nice! Your solution could be made simpler by starting i and j from 1

    public int minDistance(String word1, String word2) {
        int dp[][] = new int[word1.length()+1][word2.length()+1];
        for(int i = 1; i <= word1.length(); i++)
            for(int j = 1; j <= word2.length(); j++) 
                dp[i][j] = word1.charAt(i-1) == word2.charAt(j-1) ? dp[i-1][j-1] + 1 : Math.max(dp[i-1][j], dp[i][j-1]);
        return word1.length() + word2.length() - 2 * dp[word1.length()][word2.length()];
    }
    

  • 3

    The following coed can be used to visualize the DP matrix to debug.

            for(int i = 1; i <= word1.length(); i++){
            System.out.print(word1.charAt(i-1));
                for(int j = 1; j <= word2.length(); j++){
                    System.out.print(dp[i][j]);
                }
            System.out.println();
            }
    

    for example, when word 1 = "ear" ,word 2 = "eat".
    eat
    e111
    a122
    r122


  • 1
    H

    C++ Version

    int minDistance(string word1, string word2) {
            int m = word1.size(), n = word2.size();
            vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
            
            for(int i = 1; i <= m; i++){
                for(int j = 0; j <= n; j++){
                    dp[i][j] = word1[i-1] == word2[j-1] ? dp[i-1][j-1]+1 : max(dp[i-1][j], dp[i][j-1]);
                }
            }
            
            return m + n - 2*dp[m][n];
        }

  • 1
    K

    @jaqenhgar I made the same realization. It's a relatively straightforward application of the LCS algorithm (https://en.wikipedia.org/wiki/Longest_common_subsequence_problem). Here's my solution. It beats 90%:

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

  • 1
    G

    You only need O(n) space.

    int minDistance(string word1, string word2) {

        const auto M = word1.size();
        const auto N = word2.size();
        
        vector<int> dp(N+1, 0);
        for (auto i = 0; i < M; i++) {
            auto pre = 0;
            for (auto j = 0; j < N; j++) {
                const auto tmp = dp[j+1];
                dp[j+1] = max(dp[j+1], dp[j]);
                if (word1[i] == word2[j]) {
                    dp[j+1] = max(dp[j+1], pre + 1);
                }
                pre = tmp;
            }
        }
        
        return M + N - 2 * dp[N];
    }

  • 1
    M

    Use %2 to save space:

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

Log in to reply
 

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