DailyRNG
Login
Basic

Greedy and lazy

A repetition grabs the longest run it can. When the rest of the pattern needs less, that grab is the bug, and a mark after the repetition fixes it.

What you will see

abc

About 2 min of reading

Try It

Check the grab length.

1

Greedy length.

import re hit = re.search("<.*>", "") print(len(hit.group()))

Before you run it, say out loud what it will print. Then open the answer.

What it prints
7
2

Lazy length.

import re hit = re.search("<.*?>", "") print(len(hit.group()))

Before you run it, say out loud what it will print. Then open the answer.

What it prints
3
3

Greedy fails.

import re print(bool(re.search("a*b", "aaa")))

Before you run it, say out loud what it will print. Then open the answer.

What it prints
False
4

Class run.

import re hit = re.search("[^>]+", "") print(hit.group())

Before you run it, say out loud what it will print. Then open the answer.

What it prints
abc

Put it in order

Before you write anything, put these lines back in the right order. Click a line to move it up one step. This support step is easier than writing code from scratch, and it is here to make the last example stick.

Data Flow

A greedy repetition takes the longest run, then hands characters back one at a time while the rest of the pattern fails.
1 take the longest run
↓
2 try the rest
↓
3 fail and give one back
↓
4 stop at the first fit
Line by line

Read the first example one line at a time. A line that prints shows what appears on screen; the rest set things up quietly.

import re sets nothing on screen
hit = re.search("<.*>", "<a><b>") sets nothing on screen
print(len(hit.group())) 7
Why this works
Greedy is a default

A repetition takes the longest run and gives back only when the rest fails. That order is why a wide match swallows too much.

A class is cheaper

Excluding the ending character in a class means no give back and no backtracking. That is often clearer than a lazy mark.

Examples

Greedy takes all

import re
hit = re.search("<.*>", "<a><b>")
print(len(hit.group()))

The star takes everything to the last bracket. The match spans both tags.

Lazy takes least

import re
hit = re.search("<.*?>", "<a><b>")
print(len(hit.group()))

A question mark after the star takes the shortest run that works.

Backtracking cost

import re
hit = re.search("a*b", "aaab")
print(len(hit.group()))

The star takes three a then the b fits. No give back is needed here.

A failed give back

import re
print(bool(re.search("a*b", "aaa")))

No b exists, so the star gives back every a and still fails.

Pick by what follows

import re
hit = re.search("\d+%", "75%")
print(hit.group())

Anchoring what follows makes the greedy run the right length.

A class avoids the grab

import re
hit = re.search("[^>]+", "<abc>")
print(hit.group())

Excluding the closing character stops the run at the right place.

Words this lesson uses

Each one is defined here on this site. Open the entry for the full definition and the other words it points at.
← Case and flags
Previous Lesson
Case and flags
Next Lesson
Replacing with a pattern
Replacing with a pattern →