Java solution [longest common subsequence]


  • 2

    The remaining will be the longest common subsequence of the two input strings.

    public class Solution {
        public int minDistance(String word1, String word2) {
            int len1 = word1.length();
            int len2 = word2.length();
            
            // #1 Calculate the longest common subseq
            int[][] dp = new int[len1+1][len2+1];
            for (int row=1; row<=len1; row++) {
                for (int col=1; col<=len2; col++) {
                    dp[row][col] = word1.charAt(row-1) == word2.charAt(col-1)
                            ? dp[row][col] = dp[row-1][col-1] + 1
                            : Math.max(dp[row-1][col], dp[row][col-1]);
                }
            }
            int maxSubseq = dp[len1][len2];
            
            // #2 Calculate the required steps
            return word1.length() + word2.length() - 2 * maxSubseq;
        }
    }
    

Log in to reply
 

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