Two flavors of wildcard
Pattern matching with special symbols comes in two common forms. In glob style wildcards, a question mark matches any single character and a star matches any sequence including the empty one. In regular expression style, a dot matches any single character and a star means zero or more of the preceding element.
The boolean table
We solve both with dynamic programming over a grid of true false flags. Each cell asks whether a prefix of the text matches a prefix of the pattern.
- A literal or single character wildcard advances both by one when they agree.
- A star branches into matching zero characters or consuming one more text character.
Handling the star carefully
The two star meanings differ. The glob star stands alone and can absorb any run. The regex star binds to the symbol before it, so the cell must check whether that preceding symbol matches the current text character before extending.
Cost and seeding
We seed the table by deciding which empty matches hold, especially patterns that can match the empty string through stars. The grid is filled in order, and its final corner gives the verdict in time proportional to the product of the lengths.
Key idea
Wildcard and regex matching fill a boolean prefix grid where stars branch into skipping or consuming characters, with the regex star binding to its preceding symbol before it extends.