Config Pattern Matcher with '.' and '*'
A routing layer matches incoming paths against config patterns where '.' matches any single character and '*' matches zero or more of the preceding character. Decide whether a path matches its pattern in full.
Problem
Given an input string s and a pattern p, implement regular-expression matching with support for '.' and '*'. '.' matches any single character; '*' matches zero or more of the preceding element. The match must cover the entire input string (not partial).
Input
Two strings: s (the input, lowercase letters) and p (the pattern, lowercase letters plus '.' and '*'). Every '*' is preceded by a valid single character or '.'.
Output
A boolean: true if p matches the whole of s, else false.
Constraints
- 1 <= s.length <= 20
- 1 <= p.length <= 30
- s contains only lowercase English letters.
- p contains lowercase letters, '.', and '*'; each '*' has a valid preceding character.
Examples
Example 1
Input
s = "aab", p = "c*a*b"
Output
true
'c*' matches zero c's, 'a*' matches two a's, then 'b' matches 'b'.
Example 2
Input
s = "mississippi", p = "mis*is*p*."
Output
false
No way for the pattern to consume the whole string.