Dot-Star Pattern Match
Problem
Implement a tiny pattern matcher. In pattern, a . matches any single character, and x* (any character or . followed by a star) matches zero or more copies of x. Every other character matches itself.
Return true if the pattern matches the whole text. Every * in the pattern is guaranteed to follow a non-star character.
Example 1
- Input:
- text = "xxy", pattern = "z*x*y"
- Output:
- true
"z*" matches nothing, "x*" matches "xx" and "y" matches "y".
Example 2
- Input:
- text = "cab", pattern = "c.a*"
- Output:
- false
"c." covers "ca", and "a*" cannot produce "b".
Example 3
- Input:
- text = "ab", pattern = ".*"
- Output:
- true
".*" is any sequence of any characters.
Constraints
- 0 ≤ text.length ≤ 30
- 0 ≤ pattern.length ≤ 30
- text has lowercase letters; pattern has lowercase letters, '.' and '*'
- Each '*' follows a letter or '.'
Hint
Show the first hint
Work on suffixes: does pattern[j..] match text[i..]? The star always looks at the token 'x*' as a whole.
Walkthrough
How to approach it
01Clarify before coding
- Does the star apply to the character before it? Yes, 'x*' is one token: zero or more x.
- Must the whole text be matched? Yes, anchored at both ends.
- Is the pattern well formed? Yes, no leading star and no double star.
02Brute force
Plain recursion: at each star token, try matching zero, one, two, ... characters and recurse.
Cost: Exponential in the worst case, e.g. text 'aaaa...a' against 'a*a*a*...b' re-explores the same suffix pairs again and again.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.