Diwali Offer!Flat 20% OFF
Enroll Now
PrakalpanaLive online tech training

183. Regular Expression Matching

HardDay 54 of 60Dynamic Programming

Implement regular expression matching for a string s and a pattern p that supports two special characters: . matches any single character, and * matches zero or more copies of the character just before it. The pattern must match the whole string, not just a part of it. Return true or false.

Example 1
Input: s = "aa", p = "a"
Output: false
"a" covers only one character, not the whole string.
Example 2
Input: s = "aab", p = "c*a*b"
Output: true
c* takes zero c, a* takes "aa", then b.
Constraints
  • 1 <= s.length <= 20
  • 1 <= p.length <= 20
  • `s` has lowercase letters; `p` has lowercase letters, `.` and `*`
  • Every `*` has a valid character before it
Hints
Frequently asked at: Meta, Google, Amazon, Microsoft
Ctrl + Enter runs the examples

Not sure what to learn next?

A 1-on-1 session with an industry mentor and a roadmap built for you. How it works

  1. 1Discuss your goals
  2. 2Get a personal plan
  3. 3Start learning
Book for β‚Ή200/ 30 min