Skills101
← All coding problems

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).

Loading editor…

Log in to run and submit your code — it's free.