Search⌘ K
AI Features
Home
Courses
Grokking the Coding Interview Patterns in JavaScript

Solution: Regular Expression Matching

Explore how to implement regular expression matching with '.' and '*' using dynamic programming. Learn to optimize recursive solutions with memoization, understand how to handle pattern repetition and skipping, and efficiently determine if a string matches a given pattern. This lesson develops your ability to solve complex pattern matching problems with improved time and space complexity.

We'll cover the following...

Statement

You are given an input string, s, and a pattern string, p. Your task is to implement regular expression matching between s and p, where the pattern may include the special characters '.' and '*':

  • '.' matches any single character.

  • '*' matches zero or more occurrences of the preceding character.

The match must cover the entire input string, not just part of it.

Constraints:

  • 1≤1 \leq s.length ≤20\leq 20

  • 1≤1 \leq p.length ≤20\leq 20

  • s contains only lowercase English letters.

  • p contains only lowercase English letters, '.', and '*'.

  • It is guaranteed that for each appearance of the character '*', there will be a previous valid character to match.

Solution

One of the first ideas that comes to mind to solve ...