Matching a pattern

The last problem in the unit, and the one whose transitions need the most care per branch.

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.

1text, pattern = "aab", "c*a*b"2i, j = 2, 4                              # "aa" consumed against "c*a*"3 4repeated = pattern[j - 2]5print("pattern position", j, "holds", repr(pattern[j - 1]), "repeating", repr(repeated))6print("take none of them  -> read the cell at", (i, j - 2))7print("take one more      -> read the cell at", (i - 1, j),8      "| allowed:", repeated == "." or repeated == text[i - 1])

Two transitions out of one cell, and only the second one consumes a character of the text.

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· 5 min

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.

Python

1pattern = "a*b"2 3for count in range(4):4    print(f"a* as {count} copies ->", "a" * count + "b")5 6print("so a* consumes:", "nothing, or one or more a characters")

Printed output

Problem· 40 min

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.

1text, pattern = "aab", "c*a*b"2i, j = 2, 4 # "aa" consumed against "c*a*"3 4repeated = pattern[j - 2]5print("pattern position", j, "holds", repr(pattern[j - 1]), "repeating", repr(repeated))6print("take none of them -> read the cell at", (i, j - 2))7print("take one more -> read the cell at", (i - 1, j),8 "| allowed:", repeated == "." or repeated == text[i - 1])

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.