Preg_match_all for global matching in PHP - Time & Space Complexity

Time Complexity: Preg_match_all for global matching

O(n)

Understanding Time Complexity

We want to understand how the time it takes to find all matches in a string grows as the string gets longer.

How does the number of matches and string length affect the work done?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

$pattern = '/\d+/';
$text = 'There are 123 apples and 4567 oranges.';
preg_match_all($pattern, $text, $matches);
// $matches will hold all groups of digits found in $text
    

This code finds all groups of digits in a text string and stores them.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Scanning each character in the input string to find matches.
• How many times: Once for each character in the string, plus extra work for each match found.

How Execution Grows With Input

As the string gets longer, the function checks more characters to find matches.

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 string length.

Final Time Complexity

Time Complexity: O(n)

This means the time to find all matches grows linearly with the length of the input string.

Common Mistake

[X] Wrong: "preg_match_all runs in constant time no matter the string size."

[OK] Correct: The function must check each character to find matches, so longer strings take more time.

Interview Connect

Understanding how pattern matching scales helps you write efficient code when working with text data.

Self-Check

"What if the pattern was more complex, like including optional parts or repetitions? How would the time complexity change?"

Practice

1. What does the PHP function preg_match_all do?

easy

A. Splits a string into an array using a pattern.

B. Finds only the first match of a pattern in a string.

C. Replaces all matches of a pattern in a string with another string.

D. Finds all matches of a pattern in a string and stores them in an array.

Solution

1. Step 1: Understand the function purpose

   preg_match_all is designed to find every occurrence of a pattern in a string, not just the first one.

2. Step 2: Compare with other functions

   preg_match finds only the first match, preg_replace replaces matches, and preg_split splits strings. So only preg_match_all finds all matches and stores them.

3. Final Answer:

   Finds all matches of a pattern in a string and stores them in an array. -> Option D

4. Quick Check:

   preg_match_all = all matches found [OK]

Hint: preg_match_all finds every match, not just one [OK]

Common Mistakes:

• Confusing preg_match_all with preg_match
• Thinking it replaces matches
• Assuming it splits strings

2. Which of the following is the correct syntax to use preg_match_all in PHP?

easy

A. preg_match_all($subject, $pattern, $matches);

B. preg_match_all($pattern, $subject, $matches);

C. preg_match_all($pattern, $matches, $subject);

D. preg_match_all($matches, $pattern, $subject);

Solution

1. Step 1: Recall function parameter order

   The correct order is pattern first, then the string to search (subject), then the array to store matches.

2. Step 2: Verify options

   Only preg_match_all($pattern, $subject, $matches); follows this order: preg_match_all($pattern, $subject, $matches);

3. Final Answer:

   preg_match_all($pattern, $subject, $matches); -> Option B

4. Quick Check:

   Pattern, subject, matches array order [OK]

Hint: Pattern comes first, then string, then matches array [OK]

Common Mistakes:

• Swapping pattern and subject parameters
• Placing matches array before subject
• Using wrong parameter order

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

$text = "apple, banana, cherry";
preg_match_all('/\b\w{6}\b/', $text, $matches);
print_r($matches[0]);

medium

A. ["apple"]

B. ["apple", "banana", "cherry"]

C. ["banana", "cherry"]

D. []

Solution

1. Step 1: Understand the regex pattern

   The pattern /\b\w{6}\b/ matches words with exactly 6 letters.

2. Step 2: Check the words in the string

   "apple" has 5 letters, "banana" has 6, "cherry" has 6. So only "banana" and "cherry" match.

3. Final Answer:

   ["banana", "cherry"] -> Option C

4. Quick Check:

   Words with 6 letters = banana, cherry [OK]

Hint: Count letters to match \w{6} exactly [OK]

Common Mistakes:

• Including words with length not equal to 6
• Misunderstanding \b word boundaries
• Confusing \w with any character

4. Identify the error in this PHP code snippet using preg_match_all:

$text = "one two three";
preg_match_all('/\w+/', $matches, $text);
print_r($matches);

medium

A. The order of parameters is incorrect.

B. The regex pattern is invalid.

C. The variable $matches is not initialized.

D. The print_r function cannot print arrays.

Solution

1. Step 1: Check parameter order in preg_match_all

   The correct order is pattern, subject string, then matches array. Here, $matches and $text are swapped.

2. Step 2: Identify the impact

   Passing $matches as the subject and $text as matches causes wrong behavior and no matches found.

3. Final Answer:

   The order of parameters is incorrect. -> Option A

4. Quick Check:

   Parameter order matters in preg_match_all [OK]

Hint: Remember: pattern, subject, matches array order [OK]

Common Mistakes:

• Swapping subject and matches parameters
• Assuming regex pattern is wrong
• Thinking print_r can't print arrays

5. You want to extract all email addresses from a text using preg_match_all. Which pattern correctly matches a simple email format (letters, digits, dots, underscores before @, then domain)?

hard

A. '/[\w\.]+@[\w\.]+\.[a-z]{2,}/i'

B. '/\d+@[a-z]+\.[a-z]{2,}/'

C. '/[a-z]+@[a-z]+\.[a-z]{3}/'

D. '/\w+\s+@\s+\w+\.com/'

Solution

1. Step 1: Analyze the email pattern requirements

   Emails have letters, digits, dots, underscores before @, then domain with dot and extension.

2. Step 2: Check each pattern

   '/[\w\.]+@[\w\.]+\.[a-z]{2,}/i' matches word characters and dots before @, then domain and extension with at least 2 letters, case insensitive. Others are too restrictive or incorrect.

3. Final Answer:

   '/[\w\.]+@[\w\.]+\.[a-z]{2,}/i' -> Option A

4. Quick Check:

   Pattern includes letters, digits, dots, underscores [OK]

Hint: Use \w and dot before @, domain with dot and 2+ letters [OK]

Common Mistakes:

• Using \d+ only before @ (digits only)
• Forcing exact 3-letter domain extensions
• Adding spaces inside email pattern