Regular Expression Matching

Hard · 2-D Dynamic Programming

You are given a plain text string and a pattern string. The pattern may contain the ordinary lowercase letters, a dot that stands for any single character, and a star that means the character immediately before it can repeat zero or more times. Determine whether the pattern matches the entire text, not just part of it. Return true if it matches, false otherwise.

Examples

Input:  s = "aa", p = "a"
Output: false
Why:    The pattern has only one character and cannot stretch to cover both letters of the text.

Input:  s = "aa", p = "a*"
Output: true
Why:    The star lets the preceding 'a' repeat as many times as needed, so it can cover both letters.

Input:  s = "ab", p = ".*"
Output: true
Why:    The dot matches any character and the star lets that match repeat, covering the whole text.

Constraints

1 <= s.length <= 20, 1 <= p.length <= 20, s consists of lowercase English letters only, p consists of lowercase English letters and the characters '.' and '*', and every '*' is preceded by a valid element (letter or '.')

Practise it by voice

Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.

Practise Regular Expression Matching

This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Regular Expression Matching. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.