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

Solution: Regular Expression Matching

Explore a dynamic programming solution for matching strings with patterns containing '.' and '*' characters. Learn to efficiently manage overlapping subproblems using recursion with memoization, enabling you to handle complex pattern matching within optimal time and space constraints.

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