Regular Expression Matching
Implement regular-expression matching between a string s and a pattern p supporting exactly two special symbols: . matches any single character, and * means "zero or more copies of the character just before it". The match must cover the entire string — a partial match does not count.
So a* can match "", "a", or "aaaa"; .* can match anything; and ab*c matches "ac", "abc", "abbbc" but not "abcc".
Constraints: 1 <= s.length <= 20, 1 <= p.length <= 20; s has only lowercase letters; p has lowercase letters, ., and *, and every * has a valid character before it.
Examples
- Input:
- s = "aa", p = "a"
- Output:
- false
The pattern must cover all of s; "a" leaves the second character unmatched.
- Input:
- s = "aa", p = "a*"
- Output:
- true
The star repeats "a", covering both characters.
- Input:
- s = "ab", p = ".*"
- Output:
- true
".*" is "any character, repeated" — it can absorb the whole string.
Hints
One at a time — struggle first, peek second.
Your thinking space — verify on LeetCode, then mark it.