1143. Longest Common Subsequence

class Solution:
    def longestCommonSubsequence(self, s1: str, s2: str) -> int:
        """
        tc O(M*N) sc O(M*N)
        
        """
        m,n = len(s1), len(s2)
        dp = [[0] * (n+1) for _ in range(m+1)]
        for i in range(m):
            for j in range(n):
                if s1[i] == s2[j]:
                    dp[i+1][j+1] = dp[i][j] + 1
                else:
                    dp[i+1][j+1] = max(dp[i+1][j],dp[i][j+1])
        return dp[-1][-1]

class Solution:
    def longestCommonSubsequence(self, s1: str, s2: str) -> int:
        m,n = len(s1), len(s2)
        """
        tc O(M*N) sc O(min(M,N))
        """
        if m < n: return self.longestCommonSubsequence(s2,s1)
        dp = [0] * (n+1)
        for i in range(m):
            pre = 0
            for j in range(n):
                cur = dp[j+1] # cache current 
                dp[j+1] = max(pre+(s1[i] == s2[j]), dp[j], cur) # choose the next step optimal 1. chosee current no change 2. choose current pair with previous used number of subsequence 3. not to choose current char with index j  => use dp[j]
                pre = cur 
        return dp[n]