Regular Expression Matching

Regular Expression Matching is a Hard Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Dynamic Programming (DP) Patterns pattern, in the 2D Array (Edit Distance / Levenshtein Distance) subpattern.

Problem statement

Implement isMatch to determine whether the entire string s is described by the pattern p. Return true only when every character in s is consumed by the pattern; otherwise return false.

The pattern contains lowercase letters, ., and . A lowercase letter matches itself, while . matches any single lowercase character. The symbol applies to the immediately preceding pattern element and allows that element to occur zero or more times.

Matching is performed against all of s, not merely a prefix. Every in p is preceded by a valid pattern element, so the pattern is always structurally valid.

Example 1:

Input: s = "candle", p = "c.nd." Output: true Explanation: The dot matches a, and . matches the remaining le, so the complete string is covered.

Example 2:

Input: s = "abz", p = "a.c" Output: false Explanation: Although . can match b, the final c cannot match the final character z.

Example 3:

Input: s = "", p = "q" Output: true Explanation: The pattern element q may occur zero times, which matches the empty string.

Constraints:

- 0 <= s.length <= 20 - 0 <= p.length <= 20 - s contains only lowercase English letters - p contains only lowercase English letters, '.' and '' - Every '' in p is preceded by a valid character or '.' - The match must consume all of s

Topics and companies

Topics: Dynamic Programming, String, String Matching.

How to practise Regular Expression Matching on Thita.ai

Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(|s| * |p|) time and O(|s| * |p|) space.

Open Regular Expression Matching in the code editor, or read the Regular Expression Matching editorial for a worked solution with its approach and complexity analysis.

Where Regular Expression Matching sits in the DSA pattern sheet

Problems related to Regular Expression Matching

Other problems that use the same 2D Array (Edit Distance / Levenshtein Distance) and Dynamic Programming (DP) Patterns techniques:

Preparing this workspace.