1171. Regular Expression Matching (. and *)

Given a string s and a pattern p containing lowercase letters, '.' (matches any single character), and '*' (matches zero or more of the preceding element), determine whether p matches the entire string s. Return true or false. The input is JSON {s, p}.

Input: JSON {s, p}.

Output: Boolean — true or false.

Examples

Input: {"s":"aa","p":"a*"}
Output: true
Explanation: 'a*' matches 'aa'.

Input: {"s":"ab","p":".*"}
Output: true
Explanation: '.*' matches any string.

Input: {"s":"mississippi","p":"mis*is*p*."}
Output: false
Explanation: Pattern fails to match.

Constraints

• 0<=|s|<=1000
• 1<=|p|<=1000

Asked by