Print Longest Common Subsequence

'''
LCS variation: First find the LCS and populate the dp table as a prerequisite.
Now we have to backtrack the direction of the LCS so we will go to the right bottom of the dp table. eg i=len(s1)-1, j=len(s2)-1 then check if s1[i]==s2[j], it means that character was part of your subsequence so add it into your answer then check the left value(i,j-1) and up value(i-1,j) and check which one is higher, and update the i and j in that direciton.

The "Up" neighbor: dp[i-1][j] (The score if you ignore the current character in text1)
The "Left" neighbor: dp[i][j-1] (The score if you ignore the current character in text2)

Intution is that the LCS must have come in that direction.if up is bigger means we can get bigger LCS in the direction if we ignore ith character.Technically dp[i][j] stores the LCS of s1[:i] and s2[:j].
If the numbers Up and Left are equal, it doesn't actually matter which way you go; both paths will lead to an LCS of the same length, just potentially a different string if multiple LCS exist.
'''

def fun(str1,str2, n,m,dp):
    if n<0 or m<0:
        return 0
    if dp[n][m]!=-1:
        return dp[n][m]
    take=0
    if str1[n]==str2[m]:
        dp[n][m]=1+fun(str1,str2,n-1,m-1,dp)
    else:
        dp[n][m]=max(fun(str1,str2,n-1,m,dp), fun(str1,str2,n,m-1,dp))
    return dp[n][m]

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        dp=[[-1]*len(text2) for _ in range(len(text1))]
        ans=fun(text1,text2,len(text1)-1, len(text2)-1, dp)

        i=len(text1)-1
        j=len(text2)-1
        lca=''
        while i>=0 and j>=0:
            if text1[i]==text2[j]:
                lca+=text1[i]
                i-=1
                j-=1
            else:
                up=dp[i-1][j] if i-1>=0 else 0
                left=dp[i][j-1] if j-1>=0 else 0
                if up>left:
                    i-=1
                else:
                    j-=1
        print(''.join(reversed(lca)))

        return ans