Regular Expression Matching - Video Solutions

Problem Overview: Given a string s and a pattern p, determine if the entire string matches the pattern. The pattern supports two special characters: . which matches any single character, and * which means zero or more occurrences of the preceding element.

Approach 1: Recursive Approach with Memoization (Time: O(m*n), Space: O(m*n))

This method models the problem exactly how the pattern matching works conceptually. Start from indices i in the string and j in the pattern and recursively check if the remaining substrings match. When encountering *, two choices exist: skip the pattern segment (x*) or consume one matching character and stay on the same pattern index. Memoization stores results for states (i, j) to avoid recomputing overlapping subproblems. Without caching the recursion would explode exponentially, but memoization reduces it to O(m*n) since each state is computed once.

This approach is intuitive because it directly mirrors the matching rules of regular expressions. It is a strong choice when you want clear logic and quick implementation during interviews. The recursion depth is at most O(m + n), and the memo table ensures previously solved states are reused.

Approach 2: Dynamic Programming Tabulation (Time: O(m*n), Space: O(m*n))

The tabulation approach builds a bottom‑up DP table where dp[i][j] represents whether the first i characters of the string match the first j characters of the pattern. The transition depends on the current pattern character. If characters match directly or through ., inherit the result from dp[i-1][j-1]. If the pattern contains *, handle two cases: treat x* as zero occurrences (dp[i][j-2]) or consume one matching character if s[i-1] matches the preceding pattern character (dp[i-1][j]).

The DP table is filled row by row, carefully initializing cases where patterns like a*, a*b*, or similar can match an empty string. This approach removes recursion entirely and guarantees predictable performance with O(m*n) time and space complexity. It is often easier to debug because every subproblem is visible in the table.

Both approaches rely on breaking the problem into smaller matching states. They heavily use concepts from String processing and Dynamic Programming, while the first approach also demonstrates recursive state exploration from Recursion.

Recommended for interviews: Interviewers typically expect the dynamic programming formulation because it clearly demonstrates understanding of state transitions and overlapping subproblems. Starting with the recursive reasoning and then adding memoization shows strong problem‑solving skills, while presenting the tabulation DP proves you can convert recursive thinking into an efficient iterative solution.