Two-dimensional Dynamic Programming
Matching a pattern
The last problem in the unit, and the one whose transitions need the most care per branch.
Key idea
The state is familiar
Two inputs, so the state is the usual pair of prefixes: does the first i characters of the text match the first j of the pattern?
Nothing new there. All the difficulty is in the transition, because a pattern character can behave in several ways and one of them consumes a variable amount of text.
Why it works
Handle each feature separately, in writing
A plain character matches only itself and consumes one from each side. A single-character wildcard matches anything and does the same. Those two are one line together.
A quantifier that means zero or more of the preceding character is the hard one, and it has exactly two behaviors. It can match nothing at all, in which case both it and the character it applies to are skipped, so the answer comes from two positions earlier in the pattern with the text untouched.
Or it can absorb one more text character, provided that character is compatible with the one being repeated, in which case the pattern stays put and the text shrinks by one.
Write those three sentences before coding. The implementation is a transcription and is nearly impossible to derive at the keyboard.
Gotcha
The empty-text row is not all False
A pattern made of zero-or-more groups matches an empty text, so that row needs its own loop before the main one. Leaving it out makes every match against an empty text fail.
It steps by looking two back in the pattern, because a quantifier and the character it applies to are a unit. That pairing is why the loop starts at two rather than one.
Tip
Why the skip goes two positions
Skipping a zero-or-more group means skipping both the character and the quantifier, which is two pattern positions. Skipping only one would leave a dangling character and match nonsense.
Every place the quantifier is handled reaches back two. If a solution is off in a way that looks random, check whether one of those reaches back only one.
Gotcha
Do not try to be clever about how much to absorb
It is tempting to decide up front how many characters a quantifier should absorb. Resist it: the table already tries every possibility, because the absorb branch keeps the pattern position fixed and shrinks the text by one, which the next iteration then extends again.
That is what makes the transition correct without any search. Attempting to choose greedily produces something that works on simple patterns and fails on the ones designed to catch it.
Cost
Cost
One cell per pair of prefixes with constant work, so O(len(text) times len(pattern)) time and the same space.
The recursive form with memoization has the same complexity and is easier to write correctly under pressure, because each branch can be read as an English sentence. Either is a fine answer; say which you are writing and why.
The end of the two DP units
Every problem across both units came from the same four questions: what is a subproblem, what does its answer mean, how does it relate to smaller ones, and what is the smallest case.
Answering those in writing before touching the keyboard is the whole method. Nothing in either unit required a trick that those four questions would not produce.
Predict the output: what a star can mean
A star applies to the character before it and can stand for any number of copies, including none. Type the four lines it prints.
Regular Expression Matching
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.