Q98: Longest Common Subsequence (LCS). - DSA Patterns (Multi-Lang)

In Simple Words: 2D DP: dp[i][j] is LCS length for text1[i:] and text2[j:].

If text1[i] === text2[j]: 1 + dp[i + 1][j + 1].
Else: max(dp[i + 1][j], dp[i][j + 1]).
Time: $O(M \cdot N)$ | Space: $O(N)$

Multi-Language SolutionsPython 3 • JavaScript • TypeScript • Java • C++

Switch tabs or choose All

def longestCommonSubsequence(text1: str, text2: str) -> int:
    dp = [0] * (len(text2) + 1)
    for i in range(len(text1) - 1, -1, -1):
        prev = 0
        for j in range(len(text2) - 1, -1, -1):
            tmp = dp[j]
            if text1[i] == text2[j]:
                dp[j] = 1 + prev
            else:
                dp[j] = max(dp[j], dp[j + 1])
            prev = tmp
    return dp[0]