# How to Implement Regular Expression Matching Using Dynamic Programming: A Complete Java Guide

> Master regular expression matching with dynamic programming in Java. Build an O(m x n) DP table to handle . and * efficiently. A complete guide for interviews.

- Repository: [Kevin Naughton Jr./interviews](https://github.com/kdn251/interviews)
- Tags: how-to-guide
- Published: 2026-03-04

---

**You can solve regular expression matching in O(m×n) time by building a boolean DP table where `dp[i][j]` represents whether the first `i` characters of the input string match the first `j` characters of the pattern, handling the special characters `.` (any single character) and `*` (zero or more of the preceding element) through systematic state transitions.**

The classic regular expression matching problem requires implementing `isMatch(String s, String p)` to determine if a string matches a pattern containing `.` and `*`. According to the source code in the **kdn251/interviews** repository, the optimal solution uses a **dynamic programming** approach with a two-dimensional boolean table to eliminate exponential backtracking. This technique is implemented across multiple interview preparation packages in the repository, including the primary LeetCode solution and company-specific variants for Uber, Facebook, Twitter, and Airbnb.

## DP State Definition and Table Initialization

The foundation of the algorithm lies in defining the **DP state** precisely. Create a table `dp` with dimensions `(m+1) × (n+1)`, where `m = s.length()` and `n = p.length()`.

- **`dp[i][j]`** is `true` if the first `i` characters of `s` match the first `j` characters of `p`.
- Indices are 1-based in the table (0 represents empty prefixes).

Initialize the table by setting **`dp[0][0] = true`**, indicating that an empty string matches an empty pattern.

For the first row where `i = 0` (empty string), the only way to match a non-empty pattern is if the pattern consists of sequences like `a*b*c*`. Handle this by iterating through the pattern:

```java
for (int j = 2; j <= n; j++) {
    if (p.charAt(j - 1) == '*') {
        dp[0][j] = dp[0][j - 2];
    }
}

```

This logic, as seen in [`leetcode/dynamic-programming/RegularExpressionMatching.java`](https://github.com/kdn251/interviews/blob/main/leetcode/dynamic-programming/RegularExpressionMatching.java), checks if the current character is `*` and copies the state from two positions back, effectively treating the preceding element with `*` as zero occurrences.

## State Transition Rules

For each cell `dp[i][j]` where `i > 0` and `j > 0`, apply one of two transition rules based on the current pattern character `p.charAt(j-1)`.

### Direct Character Match or '.'

If the current pattern character is `.` (matches any single character) or matches the current string character `s.charAt(i-1)`, inherit the state from the diagonal:

```java
if (p.charAt(j-1) == '.' || p.charAt(j-1) == s.charAt(i-1)) {
    dp[i][j] = dp[i-1][j-1];
}

```

### Handling the '*' Wildcard

When `p.charAt(j-1) == '*'`, the preceding element is `p.charAt(j-2)`. This requires evaluating two mutually exclusive possibilities:

1. **Zero occurrences**: Ignore the preceding element and the `*` itself. Set `dp[i][j] = dp[i][j-2]`.

2. **One or more occurrences**: If the preceding element matches the current string character (or is `.`), carry forward the state from the row above: `dp[i][j] = dp[i][j] || dp[i-1][j]`.

The complete transition for `*` appears in the `isMatch` method across all repository variants:

```java
} else if (pc == '*') {
    // Zero occurrences of the preceding element
    dp[i][j] = dp[i][j - 2];
    
    // One or more occurrences – check preceding element
    char preceding = p.charAt(j - 2);
    if (preceding == '.' || preceding == sc) {
        dp[i][j] = dp[i][j] || dp[i - 1][j];
    }
}

```

## Complexity Analysis

The dynamic programming solution offers predictable polynomial performance:

- **Time Complexity:** **O(m × n)** where `m` is the length of the input string and `n` is the length of the pattern. Each of the `(m+1) × (n+1)` table cells is computed exactly once with O(1) operations.
- **Space Complexity:** **O(m × n)** for the full DP table. While rolling arrays can reduce this to **O(n)**, the repository implementations maintain the complete table for clarity and debugging convenience.

This complexity avoids the exponential time of naive recursive backtracking by memoizing subproblem results.

## Complete Implementation from the Repository

The following self-contained Java implementation is identical to the code found in [`leetcode/dynamic-programming/RegularExpressionMatching.java`](https://github.com/kdn251/interviews/blob/main/leetcode/dynamic-programming/RegularExpressionMatching.java) and its company-specific copies (Uber, Facebook, Twitter, Airbnb):

```java
public class RegularExpressionMatching {
    /**
     * Returns true iff the string s matches the pattern p.
     * Pattern p may contain '.' (any single char) and '*' (zero or more of preceding char).
     */
    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();

        // dp[i][j] = true if s[0..i) matches p[0..j)
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;                     // empty matches empty

        // Initialise first row (i = 0) – pattern may match empty string via '*'
        for (int j = 2; j <= n; j++) {
            if (p.charAt(j - 1) == '*') {
                dp[0][j] = dp[0][j - 2];
            }
        }

        // Fill the table
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                char pc = p.charAt(j - 1);
                char sc = s.charAt(i - 1);

                if (pc == '.' || pc == sc) {
                    // Direct match
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (pc == '*') {
                    // Zero occurrences of the preceding element
                    dp[i][j] = dp[i][j - 2];

                    // One or more occurrences – check preceding element
                    char preceding = p.charAt(j - 2);
                    if (preceding == '.' || preceding == sc) {
                        dp[i][j] = dp[i][j] || dp[i - 1][j];
                    }
                } else {
                    dp[i][j] = false; // characters do not match
                }
            }
        }
        return dp[m][n];
    }
}

```

**Usage Example:**

```java
RegularExpressionMatching matcher = new RegularExpressionMatching();
System.out.println(matcher.isMatch("aab", "c*a*b")); // true
System.out.println(matcher.isMatch("aa", "a*"));     // true
System.out.println(matcher.isMatch("ab", ".*"));     // true

```

## Summary

- **Dynamic programming** solves regular expression matching in O(m×n) time by building a boolean table where `dp[i][j]` tracks prefix matches.
- **Base cases** require initializing `dp[0][0] = true` and handling empty string matches against `*` patterns by checking `dp[0][j-2]`.
- **Transitions** depend on whether the current pattern character is a literal match/`.` (diagonal inheritance) or `*` (zero vs. one-or-more logic).
- The **kdn251/interviews** repository provides interview-ready implementations in [`leetcode/dynamic-programming/RegularExpressionMatching.java`](https://github.com/kdn251/interviews/blob/main/leetcode/dynamic-programming/RegularExpressionMatching.java) and company-specific packages under `company/{uber,facebook,twitter,airbnb}/`.

## Frequently Asked Questions

### Why use dynamic programming instead of recursion for regex matching?

Recursive backtracking explores all possible interpretations of the `*` wildcard, leading to exponential O(2^n) time in the worst case. Dynamic programming eliminates redundant calculations by memoizing the results of subproblems (prefix matches) in the `dp` table, guaranteeing polynomial O(m×n) performance as implemented in the repository's `isMatch` method.

### How does the algorithm handle the `*` character when it represents zero occurrences?

When encountering `*` at position `j-1` in the pattern, the algorithm first assumes zero occurrences of the preceding element by setting `dp[i][j] = dp[i][j-2]`. This effectively skips both the preceding character and the `*` symbol, looking up the state from two columns back in the same row.

### Can the space complexity be optimized below O(m×n)?

Yes, the space complexity can be reduced to **O(n)** or **O(min(m,n))** using rolling arrays or iterative variables, since computing row `i` only requires information from row `i-1`. However, the repository implementations in [`leetcode/dynamic-programming/RegularExpressionMatching.java`](https://github.com/kdn251/interviews/blob/main/leetcode/dynamic-programming/RegularExpressionMatching.java) maintain the full table for clarity, easier debugging, and straightforward reconstruction of the matching path.

### What is the difference between handling `.` and `*` in the DP transitions?

The `.` character acts as a wildcard for a **single** position, so the transition simply copies the diagonal value `dp[i-1][j-1]` when `pc == '.' || pc == sc`. The `*` character is a **multiplicity** operator affecting the preceding element, requiring the algorithm to evaluate two separate branches: zero occurrences (look left two columns) or one-or-more occurrences (look up one row if the preceding element matches).