Regular Expression Matching
hardDynamic Programming II+40 XPTime limit 3s
Implement a tiny regular-expression matcher. A pattern may contain:
- a lowercase letter — matches that letter
.— matches any one character*— matches zero or more copies of the element just before it (a*,.*)
Does the pattern match the entire text?
Input: two lines: the text s, then the pattern p.
Output: true or false.
Constraints: 1 ≤ length of s, p ≤ 1000; s has lowercase letters; p has lowercase letters, . and *. Every * follows a letter or a . (never at the start, never **).
Examples: aa vs a* → true; ab vs .* → true; mississippi vs mis*is*p*. → false; aab vs c*a*b → true.
Think about it: match[i][j] = does s[i:] match p[j:]? If p[j+1] is *, either skip the pair p[j]p[j+1] (match[i][j+2]) or, if p[j] matches s[i], consume one character and stay (match[i+1][j]). Otherwise the first characters must match and you move both: match[i+1][j+1]. O(|s| · |p|) — naive backtracking can be exponential.
Sample input 1
aa a*
Sample output 1
true
Sample input 2
ab .*
Sample output 2
true
Sample input 3
mississippi mis*is*p*.
Sample output 3
false
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).