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

Solution: Regular Expression Matching

Understand how to implement regular expression matching for strings and patterns including '.' and '*'. Explore recursive dynamic programming with memoization to avoid redundant calculations. Learn to decide matches by progressing through string and pattern characters, optimizing time and space complexity to O(SxP). This lesson helps you master a challenging pattern matching technique essential for coding interviews.

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