Two-sequence DP: a table of prefix pairs
Problems about two strings use a table indexed by a prefix of each. The cell compares the last characters and reads up, left and diagonal.
The pattern
Common subsequences and edit distance both index states by a pair of prefix lengths (i, j) and decide by looking at the last characters. The same table answers a family of questions about two sequences: how many times one appears in the other, whether a third string interleaves them, whether a pattern with wildcards matches, the shortest string containing both.
Two-sequence DP
dp[i][j]
- for prefixes a[:i] and b[:j]: combine dp[i − 1][j − 1] (use both last characters), dp[i − 1][j] (drop a's), dp[i][j − 1] (drop b's),
- depending on whether a[i − 1] and b[j − 1] match.
boundary
- row 0 and column 0: one string empty.
Worked example: how often does "rabbit" appear in "rabbbit"?
Count the subsequences of s equal to t. If the last characters match, either use that character of s for the last character of t, or do not: dp[i − 1][j − 1] + dp[i − 1][j]; otherwise only the second. An empty t appears once.
Rows: prefixes of rabbbit. Columns: prefixes of rabbit.
-
Step 1 / 8
Base cases filled first.
-
Step 2 / 8
Row r filled.
-
Step 3 / 8
Row a filled.
-
Step 4 / 8
Row b filled.
-
Step 5 / 8
Row b filled.
-
Step 6 / 8
Row b filled.
-
Step 7 / 8
Row i filled.
-
Step 8 / 8
Row t filled. "rabbit" appears 3 times in "rabbbit": one for each b that is left out.
How to recognise it
- Two strings or arrays, and a question about matching, aligning or combining them.
- Lengths up to about 1,000 each: O(n · m) is expected.
The problems in this module: