DSAhardStrings~35m

Clan Approved

Problem

You are an engineer on EA's Battlefield team building the clan tag validation system. Clan tags must match an admin-defined pattern before being approved. The pattern system supports two special wildcards:

'?' matches any single character exactly
'*' matches any sequence of characters (including empty)

Given a clan tag s and a pattern p, return True if the pattern matches the entire clan tag, False otherwise.

Your solution must run in O(m×n) time — naive recursive backtracking will time out on adversarial inputs.

Examples

Example 1

Input: ("abcbcd", "a*bcd")

Output: True

The * must match only 'b', leaving 'bcd' to match the rest. A greedy algorithm that tries to consume as many chars as possible with * will fail — DP explores all possibilities.

Example 2

Input: ("headshot", "h****t")

Output: True

Consecutive *s are equivalent to a single *. The DP handles this naturally — each * can match empty, so the chain collapses correctly.

Example 3

Input: ("", "***")

Output: True

Empty string matches a pattern of all stars — each * matches empty string. Base case: dp[0][j] propagates True through leading stars.

Constraints

›0 <= len(s) <= 1000
›1 <= len(p) <= 1000
›s contains only lowercase English letters
›p contains lowercase English letters, '?' and '*'

Loading question…