Regular Expressions

The java.util.regex package provides regular expression matching capability. It consists of the Pattern class (a compiled representation of a regex) and the Matcher class (a stateful engine that matches patterns against strings). Understanding how the matcher engine executes is critical to avoid CPU freezes and security issues.

Compilation and Performance

Compiling a regular expression string into a Pattern object is an expensive operation that parses the expression and builds an internal state machine.

Avoid calling String.matches(regex) inside loops, as it compiles the Pattern on every call. Instead, compile the Pattern once and store it as a static final field:

// Best practice configuration
private static final Pattern EMAIL_PATTERN = Pattern.compile("^[A-Z0-9._%+-]+@[A-Z0-9.-]+\\.[A-Z]{2,6}$", Pattern.CASE_INSENSITIVE);

Catastrophic Backtracking and ReDoS

Java's regex engine uses a backtracking NFA (Nondeterministic Finite Automaton). When evaluating complex nested quantifiers (like (a+)+) against an input that almost matches but fails at the end (e.g. aaaaaaaaaaaaaaaaaaaaaaaa!), the engine attempts to evaluate every possible branching permutation.

This results in exponential search complexity (O(2^N)), freezing the execution thread. This vulnerability is known as ReDoS (Regular Expression Denial of Service).

To prevent backtracking traps: 1. Avoid nested quantifiers like (a+)+ or (a|b). 2. Use Possessive Quantifiers (e.g., .*+, a++) or Independent/Atomic Groups (e.g., (?>a+)) which discard backtracking states once a match section completes.

Common Pitfalls

• Compiling in Loops: Calling String.matches() inside iterative loops, repeatedly rebuilding the state machine.
• ReDoS Vulnerabilities: Writing patterns with nested greedy quantifiers exposed to untrusted user inputs.
• Confusing matches() and find(): Using matches() (which requires the entire* string to match) when you only need to locate a substring (which should use find()).

Best Practices

• Declare Pattern variables as private static final constants to reuse compiled instances.
• Use possessive quantifiers (e.g., ++ or *+) to optimize matching speed and prevent ReDoS.
• Use find() for matching substrings and matches() only for full-string validation.

Interview-Relevant Information