1143. Longest Common Subsequence

Given two strings text1 and text2, return the length of their longest common subsequence.

dynamic programming, memorize previous results

Let dp[i][j] represents the lcs between the text1 substring ends at index i-1 and text2 substring ends at index j-1, dp[0][j]=0, dp[i][0]=0;

//if last character at the last index is different
if (text1[i-1]!=text2[j-1]){
    dp[i][j]=max(dp[i-1][j], dp[i][j-1]);
}

// if the last character is the same
if (text1[i-1]!=text2[j-1]){
    dp[i][j]=dp[i-1][j-1]+1, dp[i][j-1];
}

iteration

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int[][] memo = new int[text1.length()+1][text2.length()+1];
        for( int i =1;i<memo.length; i++){
            for(int j=1; j<memo[0].length; j++){
                if(text1.charAt(i-1)==text2.charAt(j-1)) 
                    memo[i][j]=memo[i-1][j-1]+1;
                else
                    memo[i][j]=Math.max(memo[i-1][j],memo[i][j-1]);
            }
        }
        
        return memo[text1.length()][text2.length()];
    }
}

memory optimized solution: memory O(min(text1.length, text2.length)

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        
        // make text2 always shorter than text1
        if (text1.length()<text2.length()){
            return longestCommonSubsequence(text2, text1);
        }
        int len1 = text1.length()+1;
        int len2 = text2.length()+1;
        
        int[] memo= new int[len2];
        int topLeft = 0;
        for (int i=1; i<len1; i++){
            for (int j=1; j<len2; j++){
                // temp is the value of next topLeft;
                // value of memo[j] is current top;
                int temp = memo[j];
                if(text1.charAt(i-1)==text2.charAt(j-1)){
                    memo[j] = topLeft+1;
                }else{
                    memo[j] = Math.max(memo[j-1], memo[j]);
                }
                topLeft=temp;
            }
            // initialize the value after scanning text2;
            topLeft=0;
        }
        return memo[len2-1];

    }
}