Show problems as
Classic problem #10HardStringDynamic ProgrammingRecursion

Regular Expression Matching

Real-world version: Mask Matches The Whole Code
Tracked in this browser only
Read Regular Expression Matching on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Learn the pattern firstRegular Expressions · Strings, animated step by step

A parts catalogue lets a technician look up stock with a mask instead of an exact serial. You are given a serial code of lowercase letters and a mask mask, and you have to decide whether the mask describes that serial.

Read mask left to right as a run of items. An item is one lowercase letter, which stands for that letter alone, or '.', which stands for any one letter. Writing '*' straight after an item says that the item is used some number of times over, possibly not at all. Every '*' in mask is guaranteed to follow an item.

Return true when the items account for code from its first letter through its last, with nothing left over on either side, and false otherwise. Covering a leading chunk of code is not enough.

Examples

Example 1

Input
code = "harp", mask = "hz*arp"
Output
true

The item z is used zero times over, so the mask boils down to h, a, r, p, which lines up with the serial.

Example 2

Input
code = "harp", mask = "h.r."
Output
true

Each dot stands in for one letter, so the four items cover all four letters of the serial.

Example 3

Input
code = "harp", mask = "har"
Output
false

The items only reach the first three letters and nothing accounts for the trailing p.

Constraints

  • 1 <= code.length <= 20
  • 1 <= mask.length <= 20
  • code contains only lowercase English letters.
  • mask contains only lowercase English letters, '.', and '*'.
  • Every appearance of '*' is preceded by a valid item.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def mask_matches(code: str, mask: str) -> bool:
Java
public boolean maskMatches(String code, String mask)

More on the same topics