The Question

Regular Expression Matching

Given an input string s and a pattern p, implement a function to determine if s matches p exactly. The pattern supports the following special characters: - . matches any single character. - * matches zero or more of the preceding element. The matching should cover the entire input string (not partial). Example 1: Input: s = "aa", p = "a" Output: true Example 2: Input: s = "ab", p = "." Output: true Constraints: - 1 <= s.length <= 20 - 1 <= p.length <= 30 - s contains only lowercase English letters. - p contains lowercase English letters, '.', and ''. - It is guaranteed for each appearance of the character '', there will be a previous valid character to match.

Java

Questions & Insights

Clarifying Questions

What are the maximum lengths of the input string `s` and the pattern `p`?

Assumption: Both strings will have a length between 0 and 20-30, which is typical for this complexity class.

Can the pattern `p` be malformed, such as starting with `*` or having consecutive `?**

Assumption: The pattern will be valid according to standard regex rules (a will always follow a valid preceding character).

What is the character set for `s` and `p`?

Assumption: Both contain only lowercase English letters, ., and .

Is the matching case-sensitive?

Assumption: Yes, although the current constraints imply only lowercase letters.

Thinking Process

Identify the recursive structure: The problem can be broken down into subproblems by comparing the start of the string and pattern. If the second character of the pattern is , we have two choices: ignore the and the preceding character (0 occurrences), or match the current character and continue using the pattern for the rest of the string (1 or more occurrences).

Handle the `.` wildcard: A . in the pattern matches any single character in s. This simplifies the "first character match" logic to (s[i] == p[j] || p[j] == '.').

Optimize with Dynamic Programming: A simple recursive approach would result in exponential time complexity due to overlapping subproblems (especially with multiple ). Using a 2D memoization table (or DP array) of size (N+1) x (M+1) stores whether s[i...] matches p[j...], reducing the complexity to

O(N \times M)

Iterative vs. Recursive: While both work, an iterative bottom-up approach is often preferred in Java to avoid StackOverflowError for deep recursion, though with

N, M \le 30

, top-down memoization is equally safe and often more intuitive to implement.

Implementation Breakdown

Problem Set

Functional Requirements:

Implement isMatch(String s, String p).

Support . for any character.

Support for zero or more of the preceding character.

Must match the entire string s.

Constraints:

Time complexity should be

O(N \times M)

Space complexity should be

O(N \times M)

to store the DP state.

Approach

Algorithm: Dynamic Programming (Bottom-Up).

Data Structure: 2D boolean array dp[s.length + 1][p.length + 1].

Complexity:

Time:

O(N \times M)

where

N

is length of

s

and

M

is length of

p

Space:

O(N \times M)

for the DP table.

Implementation

Wrap Up

Advanced Topics

Readability vs. Performance: The bottom-up DP is

O(NM)

space. If memory is a concern, notice that dp[i] only depends on dp[i-1] and dp[i]. We could optimize space to

O(M)

using two rows.

NFA Construction: For a more "production-grade" regex engine, one might convert the pattern into a Non-deterministic Finite Automaton (NFA). This is how libraries like java.util.regex or Grep (using Thompson's construction) handle more complex patterns.

Backtracking with Pruning: While DP is standard for this specific problem, backtracking with memoization is often easier to extend if we were to add more complex features like capture groups or backreferences.