Character classes and quantifiers in PHP - Time & Space Complexity

Time Complexity: Character classes and quantifiers

O(n)

Understanding Time Complexity

When using character classes and quantifiers in PHP regular expressions, it's important to understand how the matching process scales as the input grows.

We want to know how the time to find matches changes when the input string gets longer.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

$pattern = '/[a-z]{3,5}/';
$input = str_repeat('abc', 1000);
if (preg_match_all($pattern, $input, $matches)) {
    // matches found
}
    

This code searches for sequences of 3 to 5 lowercase letters in a long repeated string.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The regex engine checks each position in the input string to see if the pattern matches.
• How many times: It tries to match starting at almost every character, so roughly once per character in the input.

How Execution Grows With Input

As the input string gets longer, the regex engine does more checks, roughly one per character.

Input Size (n)	Approx. Operations
10	About 10 checks
100	About 100 checks
1000	About 1000 checks

Pattern observation: The work grows roughly in direct proportion to the input size.

Final Time Complexity

Time Complexity: O(n)

This means the time to find matches grows linearly as the input string gets longer.

Common Mistake

[X] Wrong: "Using quantifiers always makes regex slow and exponential."

[OK] Correct: Simple quantifiers like {3,5} on character classes usually cause only linear checks, not exponential backtracking.

Interview Connect

Understanding how regex matching time grows helps you write efficient patterns and explain your code clearly in interviews.

Self-Check

"What if we changed the quantifier from {3,5} to .*? How would the time complexity change?"

Practice

1. Which character class in PHP regex matches any digit from 0 to 9?
/[?]/

easy

A. \\D

B. \\w

C. \\s

D. \\d

Solution

1. Step 1: Understand character classes

   In PHP regex, \\d matches any digit (0-9), \\w matches word characters, \\s matches whitespace, and \\D matches non-digits.

2. Step 2: Identify the digit matcher

   The class that matches digits is \\d.

3. Final Answer:

   \\d -> Option D

4. Quick Check:

   Digits = \\d [OK]

Hint: Remember: \d = digit, \w = word, \s = space [OK]

Common Mistakes:

• Confusing \d with \w
• Using \D to match digits
• Mixing up \s with digit class

2. Which of the following is the correct syntax to match exactly three lowercase letters using PHP regex?

easy

A. /[a-z]{3}/

B. /[a-z]{,3}/

C. /[a-z]{3,}/

D. /[a-z]{3,5}/

Solution

1. Step 1: Understand quantifiers

   Curly braces {n} specify exact count. {3} means exactly 3 times.

2. Step 2: Match exactly three lowercase letters

   The pattern /[a-z]{3}/ matches exactly three lowercase letters.

3. Final Answer:

   /[a-z]{3}/ -> Option A

4. Quick Check:

   Exact 3 lowercase letters = /[a-z]{3}/ [OK]

Hint: Use {n} for exact count in regex quantifiers [OK]

Common Mistakes:

• Using {,3} which is invalid syntax
• Using {3,} which means 3 or more
• Using {3,5} which means 3 to 5 times

3. What will be the output of this PHP code?

$pattern = '/\d{2,4}/';
$string = 'Year 2023 and 99 problems';
preg_match_all($pattern, $string, $matches);
print_r($matches[0]);

medium

A. ["20", "23", "99"]

B. ["2023", "99"]

C. ["202", "3", "99"]

D. ["2", "0", "2", "3", "9", "9"]

Solution

1. Step 1: Understand the regex pattern

   The pattern /\d{2,4}/ matches sequences of digits between 2 and 4 digits long.

2. Step 2: Apply pattern to string

   In 'Year 2023 and 99 problems', '2023' (4 digits) and '99' (2 digits) match. Smaller digit groups like '2' or '3' alone do not match.

3. Final Answer:

   ["2023", "99"] -> Option B

4. Quick Check:

   Digits 2-4 long = ["2023", "99"] [OK]

Hint: Quantifier {2,4} matches digit groups length 2 to 4 [OK]

Common Mistakes:

• Splitting digits into smaller groups
• Ignoring quantifier range
• Assuming single digits match

4. Identify the error in this PHP regex pattern:

$pattern = '/[a-z]{2,1}/';

medium

A. Quantifier range is invalid; min cannot be greater than max

B. Character class brackets are missing

C. Pattern should use double quotes instead of single quotes

D. No error; pattern is valid

Solution

1. Step 1: Analyze quantifier syntax

   The quantifier {2,1} means minimum 2 and maximum 1 repetitions, which is invalid because min > max.

2. Step 2: Confirm error type

   Regex quantifiers must have min ≤ max. This causes a syntax error.

3. Final Answer:

   Quantifier range is invalid; min cannot be greater than max -> Option A

4. Quick Check:

   Min > max in {2,1} is invalid [OK]

Hint: Quantifier {min,max} must have min ≤ max [OK]

Common Mistakes:

• Swapping min and max values
• Ignoring quantifier syntax rules
• Assuming pattern is valid without checking quantifiers

5. You want to match a string that contains exactly 3 to 5 uppercase letters followed by 2 digits in PHP regex. Which pattern is correct?

hard

A. /^[A-Z]{3,5}\d{1,2}$/

B. /^[A-Z]{2,3}\d{5}$/

C. /^[A-Z]{3,5}\d{2}$/

D. /^[A-Z]{3,5}\d{3}$/

Solution

1. Step 1: Understand the requirements

   The string must start (^) with 3 to 5 uppercase letters [A-Z]{3,5} and end ($) with exactly 2 digits \d{2}.

2. Step 2: Match pattern to options

   /^[A-Z]{3,5}\d{2}$/ matches exactly 3-5 uppercase letters followed by exactly 2 digits, anchored start and end.

3. Final Answer:

   /^[A-Z]{3,5}\d{2}$/ -> Option C

4. Quick Check:

   3-5 uppercase + 2 digits = /^[A-Z]{3,5}\d{2}$/ [OK]

Hint: Use anchors ^ and $ to match whole string exactly [OK]

Common Mistakes:

• Mixing digit counts in quantifiers
• Omitting anchors causing partial matches
• Using wrong quantifier ranges