Problem statement

https://leetcode.com/problems/longest-common-subsequence/

Solution

See also very similar Problem 0583 Delete Operation for Two Strings. The logic here is almost the same.

Complexity

Time complexity is O(mn), space complexity is O(mn) as well, which can be reduced to O(m + n).

Code

class Solution:
    def longestCommonSubsequence(self, text1,text2):
        text1 = "!" + text1
        text2 = "!" + text2
        m, n = len(text1), len(text2)
        dp = [[0] * n for _ in range(m)]
        dp[0][0] = 1
        for i, j in product(range(m), range(n)):
            if text1[i] == text2[j]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])

        return dp[-1][-1] - 1