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

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:

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, 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:

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:

} 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 and its company-specific copies (Uber, Facebook, Twitter, Airbnb):

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:

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

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}