LeetCode 1143 Longest Common Subsequence - Implementation

function longestCommonSubsequence(text1, text2)
    m := length of text1
    n := length of text2
    dp := 2D (two-dimensional) array of size (m + 1) x (n + 1), all 0
    for i from 1 to m
        for j from 1 to n
            if text1[i - 1] = text2[j - 1] then
                dp[i][j] := dp[i - 1][j - 1] + 1
            else
                dp[i][j] := max(dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]

Time: $O(mn)$. Space: $O(mn)$, reducible to $O(\min(m, n))$.

When characters match, extend the LCS from dp[i-1][j-1]. When they don't, take the better of skipping either character.

This is the foundation for many string problems. Edit distance, shortest common supersequence, and diff algorithms all build on LCS.