hardDynamic Programming 2DAI-applied~44 min
Guardrail Pattern Match
A safety layer validates a model's output against a guardrail pattern that allows '.' (any single character) and '*' (zero or more of the preceding character). Decide whether the full output matches the pattern.
Problem
Implement regular-expression matching for '.' and '*' covering the entire input. '.' matches any single character; '*' matches zero or more of the element immediately before it. Return true if pattern p matches the whole string s.
Input
Strings s (0 ≤ |s| ≤ 20) and p (0 ≤ |p| ≤ 30); p's '*' always follows a valid element.
Output
A boolean — true if p matches all of s.
Constraints
- The match must cover the entire string, not a substring
- '*' applies to the single preceding element and can match zero copies
- Lowercase letters plus '.' and '*'
Examples
Example 1
Input
s = "aab", p = "c*a*b"
Output
true
c* matches zero c's, a* matches 'aa', then 'b'.
Example 2
Input
s = "mississippi", p = "mis*is*p*."
Output
false
The pattern cannot consume the whole string.