Short java DP solution O(n) space (48ms)


  • 3
    Y
    public int minDistance(String word1, String word2) {
            int[] dp = new int[word2.length()];
            int lcs = 0;
            for(int i = 0; i < word1.length(); i++){
                int cur_max = 1;
                for(int j = 0; j < word2.length(); j++){
                    int temp = dp[j];
                    if(word2.charAt(j) == word1.charAt(i)) dp[j] = cur_max;
                    cur_max = Math.max(temp+1, cur_max);
                    lcs = Math.max(lcs, dp[j]);
                }
            }
            return word1.length() - lcs + word2.length() - lcs;
        }
    

    Use O(n) space, in i-th iteration over word1, update max possible length of common subsequence end up with word1.charAt(i) in word2 and store in the dp array.


  • 0
    S

    awesome solution


Log in to reply
 

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