Regular Expression Matching
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).

30:00

Regular Expression Matching
hard
Topics
Companies

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

Example 1:
Input: {"s":"aa","p":"a*"}
Output: true
Constraints:

  • 1≤s.length≤201 \leq s.\text{length} \leq 20

  • 1≤p.length≤201 \leq p.\text{length} \leq 20

  • s consists of lowercase English letters.

  • p consists of lowercase English letters, '.', and '*'.

  • It is guaranteed that for each *, there will be a valid preceding character.

Input
arr ={"s":"aa","p":"a*"}

Initialize DP. s="aa" (len 2), p="a*" (len 2)

String s
a
a
Pattern p
a
*
DP[i][j] = s[0..i-1] matches p[0..j-1]
ε
a
*
ε
T
F
F
a
F
F
F
a
F
F
F

Result: No Match

* = zero or more. = any char
Variables
No variables to display
DepthFunction Call
Stack empty
0/5