Hard · Dynamic Programming

Regular Expression Matching

Given a string s and a pattern p in which '.' matches any single character and '*' matches zero or more copies of the element just before it, return true if p matches the entire string s (not just a prefix), else false.

Examples

Example 1

{
  "s": "aa",
  "p": "a*"
}

Output: true

Example 2

{
  "s": "ab",
  "p": ".*"
}

Output: true

Rebuild it in the studio

Read every interview problem free. Ten rooms need no account. A token opens a problem in full — Pro never counts.