Patterns with placeholders
Wildcard matching asks whether a pattern matches a whole string when the pattern may contain two special symbols:
- A question mark matches exactly one character of any kind.
- A star matches any sequence, including the empty sequence, of characters.
The star is what makes this tricky, because it can absorb zero, one, or many characters, and a greedy guess can be wrong.
The dynamic program
Define whether the first i characters of the string match the first j characters of the pattern. Process pattern and string positions and fill a table of true and false values:
- A plain character or a question mark matches when the current characters line up, so the cell follows the diagonal.
- A star offers two paths: treat it as matching nothing, taking the value from one pattern character earlier, or have it consume one more string character, taking the value from one string character earlier. The cell is true if either path is true.
The base row handles a pattern of leading stars matching the empty string. The answer sits in the cell covering both full lengths.
Key idea
Wildcard matching fills a true or false table where a question mark follows the diagonal and a star is true if it matches nothing or consumes one more character; the corner cell decides the full match.