LeetCode 1143: Longest Common Subsequence

Dynamic Programming

Subproblem

Say input strings are $x[1 \ldots m]$ and $y[1 \ldots n]$ . Let $L(i, j)$ be the length of the longest common subsequence between the pair of prefixes $x[1 \ldots i]$ and $y[1 \ldots j]$ .

$L(i, j) = \begin{cases} 0, & \text{if } i = 0 \text{ or } j = 0 \\ 1+L(i-1, j-1), & \text{if } x[i] = y[j] \\ \max\left( \left\{ L(i-1, j), L(i, j-1) \right\} \right) & \text{otherwise} \end{cases}$

$L(m, n)$ is the solution.

Order

Subproblems on a $(m \times n)$ -grid and row-wise processing gives a topological ordering.

Time: $\mathcal{O}(m \cdot n)$ , space: $\mathcal{O}(m \cdot n)$ .

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        x, y = text1, text2
        m, n = len(x), len(y)
        dp = [
            [float('-inf')]*(n+1) for _ in range(m+1)
        ]
        for c in range(n+1):
            dp[0][c] = 0
        for r in range(m+1):
            dp[r][0] = 0
        for r in range(1, m+1):
            for c in range(1, n+1):
                i, j = r-1, c-1
                if x[i] == y[j]:
                    dp[r][c] = 1 + dp[r-1][c-1]
                else:
                    dp[r][c] = max( dp[r-1][c], dp[r][c-1] )
        return dp[m][n]

A subproblem depends on the subproblems that are on the same row or on the previous row. So, we keep track of just two rows and reuse.

Time: $\mathcal{O}(m \cdot n)$ , space: $\mathcal{O}(n)$ .

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        x, y = text1, text2
        m, n = len(x), len(y)
        dp = [
            [float('-inf')]*(n+1) for _ in range(2)
        ]
        for c in range(n+1):
            dp[0][c] = 0
        dp[0][0], dp[1][0] = 0, 0
        prev_row, curr_row = 0, 1
        for r in range(1, m+1):
            for c in range(1, n+1):
                i, j = r-1, c-1
                if x[i] == y[j]:
                    dp[curr_row][c] = 1 + dp[prev_row][c-1]
                else:
                    dp[curr_row][c] = max( dp[prev_row][c], dp[curr_row][c-1] )
            prev_row, curr_row = curr_row, prev_row
        return dp[prev_row][n]

unreasonably effective