ProblemNest
Sign In
You are coding as a Guest. Sign in with your RoleNest account to permanently track your streak, earn XP, and climb the Campus Leaderboard!
Sign In with RoleNest
🔥Regular Expression Matching: Recursive Wildcard DPHard
SUPER HARD PROBLEM OF THE DAY+150 XP • FAANG OA TIER

High-difficulty challenge matching authentic Google, Amazon & Uber L5 online assessment conditions.

HardDynamic Programming•Acceptance: 28.5%

Regular Expression Matching: Recursive Wildcard DP

Targeted in FAANG & Tech OA:GoogleMicrosoftUber
Real-World Engineering Context
Foundation of regex parser engines in web browsers (V8 JavaScript RegExp engine, WebKit) and lexer tokenizers in compilers.
Given an input string `s` and a pattern `p`, implement regular expression matching with support for `'.'` and `'*'` where: - `'.'` Matches any single character. - `'*'` Matches zero or more of the preceding element. The matching should cover the entire input string (not partial).

Sample Test Cases

Input: ["aa","a*"]
Expected: true
Input: ["ab",".*"]
Expected: true
Input: ["mississippi","mis*is*p*."]
Expected: false

Constraints

  • 1 <= s.length <= 20
  • 1 <= p.length <= 20
  • s contains only lowercase English letters.
  • p contains only lowercase English letters, '.', and '*'.
  • It is guaranteed for each appearance of the character '*', there will be a previous valid character to match.
Recruiter Fast-Track ReferralVerified Candidate
Direct pipeline to Google, Amazon, Microsoft, Swiggy, & Uber recruiters
DevScore: 750/1000

Top DevScore profiles bypass resume screening filters. Every verified problem solve writes authentic proof-of-work to your profile and dispatches you directly into employer inboxes on RoleNest.

Explore 5,000+ Direct ATS Openings on RoleNest ↗✓ Direct Referral Active