Lazy (Non-Greedy) Quantifiers

By default, regex quantifiers are greedy: they consume as much as possible, then back off only if needed for the rest of the pattern to match.

.*x  on  'abxcxdx'  →  '.*' matches 'abxcxd', then 'x' matches the final x

Append ? to make a quantifier lazy (also called non-greedy or reluctant): consume as little as possible, then expand only if needed.

.*?x on  'abxcxdx'  →  '.*?' matches 'ab', then 'x' matches the first x

The full set

When lazy matters

The classic HTML-tag extraction:

The second is what you almost always want.

Quoted strings:

Implementation

In a backtracking engine, the only difference between greedy and lazy is the ORDER of attempts:

In an NFA simulator the priority is encoded in the epsilon-closure order: for greedy *, the 'loop again' epsilon is tried before 'exit'; for lazy *?, the 'exit' epsilon is tried first.

Lazy quantifiers do NOT change runtime complexity — both greedy and lazy NFA simulation are O(n·m). They only change WHICH match is returned when multiple are possible.

Gotcha

Lazy quantifiers do not always match the 'smallest' overall string. They match the leftmost match, with the lazy parts minimal given that left most match is fixed. Example:

If you want truly 'shortest', that's a different algorithm — not expressible in standard regex.