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

Solution: Regular Expression Matching

Explore how to implement regular expression matching using dynamic programming by handling '.' and '*' characters. Understand the recursive approach with memoization to avoid redundant calculations, improving time complexity from exponential to polynomial. This lesson helps you master the technique of matching patterns against strings while optimizing for interview coding challenges.

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