Length of Longest Common Subsequence (LCS) and Longest common subsequence string leetcode

Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

For example, "ace" is a subsequence of "abcde".
A common subsequence of two strings is a subsequence that is common to both strings.

Example 1:

Input: text1 = "abcde", text2 = "ace" 
Output: 3  
Explanation: The longest common subsequence is "ace" and its length is 3.

Solution:
Bottom up Approach(Memoization) :
Time complexity : O(m*n) where is m and n is the length of two strings a and b
space complexity : o(m*n) for using 2d dp and O(m+n) for auxiliary stack space because in worst case we will make m+n recursive calls.

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
         // we will start with the last index if its a match then we will decrement both the index
        //else we will decrement text1 index keeping text2 index same and in second method call we will decrement text2 index keeping the text1 index same 
        // by this we will cover all the possibility
        // and we will be  able to get substring with the largest length common in both the Strings
        // lets optimize with dp
        int dp[][] = new int[text1.length()][text2.length()];
        for(int row[]: dp) Arrays.fill(row,-1);
        return findLcsLength(text1,text2,text1.length()-1,text2.length()-1,dp);
    }
    public int findLcsLength(String a, String b, int i,int j,int dp[][]){
        if(i<0 || j<0) return 0;
        if(dp[i][j]!=-1) return dp[i][j];
        if(a.charAt(i) ==b.charAt(j)){
            return dp[i][j] =  1 + findLcsLength(a,b,i-1,j-1,dp);
        }
        else {
            return dp[i][j]= 0+Integer.max(findLcsLength(a,b,i-1,j,dp),findLcsLength(a,b,i,j-1,dp));
        }

    }
}

Tabulation

class Solution {
    public int longestCommonSubsequence(String str1, String str2) {
     int dp[][] = new int[str1.length()+1][str2.length()+1];
     for(int i=0;i<=str1.length();i++){
                dp[i][0] =0;
            }
            for( int i =0;i<=str2.length();i++){
                dp[0][i] = 0;
            }

            for( int i =1;i<=str1.length();i++){
                for(int j =1;j<=str2.length();j++){
                    if(str1.charAt(i-1)==str2.charAt(j-1)){
                        dp[i][j] = 1 + dp[i-1][j-1];
                    }
                    else dp[i][j] = Integer.max(dp[i][j-1],dp[i-1][j]);
                }
            }
    return dp[str1.length()][str2.length()];
    }
}

If we have to print the longest common subsequence string, just add the following in the above code.

int p = str1.length(), q = str2.length();
        while(p>0 && q>0){
            if(str1.charAt(p-1) == str2.charAt(q-1)){
                str = str1.charAt(p-1)+ str;
                p--;
                q--;

            }
            else if(dp[p][q-1] > dp[p-1][q]){
                q--;
            }
            else p--;
        }
        System.out.println(str);