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

Solution: Regular Expression Matching

Explore how to implement a solution for regular expression matching between a string and a pattern using dynamic programming. Understand how memoization helps optimize recursive calls and manages patterns containing '.' and '*'. This lesson helps you grasp handling complex pattern matching efficiently by reducing redundant computations and evaluating all valid matching scenarios.

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