Longest Common Subsequence

[fbaquant]

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

[fbaquant]

Approach

Let $X$ be XMJYAUZ and $Y$ be MZJAWXU. The longest common subsequence between $X$ and $Y$ is MJAU. The following table shows the lengths of the longest common subsequences between prefixes of $X$ and $Y$. The $i$-th row and $j$-th column show the length of the LCS between $X{1..i}$ and $Y{1..j}$.

Code

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        if len(text1) < len(text2):
            text1, text2 = text2, text1

        n, m = len(text1), len(text2)
        dp = [[0 for _ in range(m + 1)] for _ in range(2)]    # need only two rows when updating

        for i in range(1, n + 1):
            for j in range(1, m + 1):
                if text1[i - 1] == text2[j - 1]:
                    dp[1 - i % 2][j] = dp[i % 2][j - 1] + 1
                else:
                    dp[1 - i % 2][j] = max(dp[i % 2][j], dp[1 - i % 2][j - 1])

        return dp[1 - n % 2][-1]