Regular Expression Matching
HardDynamic Programming
Implement a small regular-expression matcher. Given a string s and a pattern p, return True if p matches all of s, and False otherwise. Matching only part of s does not count.
The pattern is made of these pieces:
- a lowercase letter matches exactly that letter;
.matches any single character;x*(a letter or.followed by*) matches zero or more copies ofx. For exampleb*matches"","b"or"bbbb", and.*matches any string, including the empty one.
A * always belongs to the character directly before it; it never appears at the start of p and never follows another *.
Example 1
- Input:
- s = "abbbc", p = "ab*.c"
- Output:
- True
- Explanation
amatchesa, thenb*takes two of the threebs,.takes the thirdb, andcmatchesc. The trick is thatb*must not be greedy here: if it ate all threebs,.would have to matchcand the finalcwould have nothing left.
Example 2
- Input:
- s = "ab", p = ".*c"
- Output:
- False
- Explanation
.*can absorbab, but the pattern still needs a literalcat the end andshas none, so no split works.
Example 3
- Input:
- s = "aaa", p = "ab*a*"
- Output:
- True
- Explanation
- The first
amatchesa,b*matches zerobs, anda*absorbs the remainingaa.
Constraints
1 <= s.length <= 201 <= p.length <= 20scontains only lowercase English letterspcontains only lowercase English letters,.and*- Every
*inpis preceded by a letter or.