state 19 of 32 · 5 min

One grid, several questions

The two sequence grid answers more than the longest common subsequence, and recognising a problem as this shape saves deriving it.

The base

python

def lcs(a, b):
    n, m = len(a), len(b)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if a[i-1] == b[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[n][m]

Shortest common supersequence

The shortest string containing both as subsequences:

code

len(a) + len(b) - lcs(a, b)

The common part is written once instead of twice.

Minimum deletions to make two strings equal

code

(len(a) - lcs) + (len(b) - lcs)

Everything not in the common subsequence has to go, from both sides.

Longest common substring, which is different

Contiguity changes the recurrence. A mismatch resets to zero rather than carrying the best forward:

python

def lcsubstring(a, b):
    best = 0
    dp = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    for i in range(1, len(a) + 1):
        for j in range(1, len(b) + 1):
            if a[i-1] == b[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
                best = max(best, dp[i][j])
            # else: stays 0, the run is broken
    return best

And the answer is the maximum anywhere, not the last cell, because the best run may end in the middle. Same distinction as the increasing subsequence table.

Question	Change
Longest common subsequence	max of the two neighbours on mismatch
Longest common substring	reset to 0 on mismatch, answer is the max cell
Shortest common supersequence	derived from the LCS length
Minimum deletions	derived from the LCS length
Longest palindromic subsequence	LCS of the string and its reverse

Distinct subsequences

"How many ways does b appear as a subsequence of a" is a counting version:

python

dp[i][j] = dp[i-1][j] + (dp[i-1][j-1] if a[i-1] == b[j-1] else 0)

Addition instead of maximum, again the counting against optimising distinction.

Wildcard and regular expression matching

Also this grid, with the operator replaced by a boolean or and extra cases for the pattern characters. * matching any sequence means a cell can come from the cell above, which is what "consume one more character and stay on this pattern position" looks like.