Show problems as
Classic problem #44HardStringDynamic ProgrammingGreedyRecursion

Wildcard Matching

Real-world version: Dispatch Rule Match
Tracked in this browser only
Read Wildcard 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

An event router picks a destination by testing an incoming event's key against a subscription rule.

The key is plain text. The rule is plain text too, except that it may carry two wildcard symbols:

  • ? stands in for exactly one character of the key.
  • * stands in for a stretch of the key of any length, and a stretch of length zero is allowed.

The router fires only on a total fit: reading the rule left to right must consume the key from its first character through its last, with nothing of the key spilling past the end of the rule and nothing of the rule left dangling once the key is used up.

Return true when rule fires on key, and false when it does not. Either text may be empty.

Examples

Example 1

Input
key = "deploy", rule = "d*y"
Output
true

The wildcard soaks up `eplo`, leaving `d` and `y` to line up with the two ends of the key.

Example 2

Input
key = "deploy", rule = "d?ploy?"
Output
false

The first `?` takes `e` and the literals take `ploy`, but the trailing `?` still demands a character and the key has run dry.

Example 3

Input
key = "", rule = "***"
Output
true

Each wildcard is free to stand in for a stretch of length zero, so an empty key is a total fit.

Constraints

  • 0 <= key.length, rule.length <= 2000
  • key holds lowercase letters only
  • rule holds lowercase letters, '?' and '*' only

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 rule_fires(key: str, rule: str) -> bool:
Java
public boolean ruleFires(String key, String rule)

More on the same topics