Preg_replace for substitution in PHP - Time & Space Complexity

Time Complexity: Preg_replace for substitution

O(n)

Understanding Time Complexity

When using preg_replace in PHP, it's important to know how the time it takes grows as the input gets bigger.

We want to understand how the number of replacements affects the work done.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

$string = "apple banana apple grape apple";
$pattern = '/apple/';
$replacement = 'orange';
$result = preg_replace($pattern, $replacement, $string);
    

This code replaces every occurrence of "apple" with "orange" in the given string.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The function scans the entire string to find matches for the pattern.
• How many times: It checks each character in the string, and for each match, it performs a replacement.

How Execution Grows With Input

The time taken grows roughly in proportion to the length of the string because every character is checked.

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

Pattern observation: Doubling the string length roughly doubles the work done.

Final Time Complexity

Time Complexity: O(n)

This means the time to complete grows linearly with the size of the input string.

Common Mistake

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

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

Interview Connect

Understanding how pattern matching scales helps you explain performance when working with text processing in real projects.

Self-Check

"What if the pattern was more complex and used backreferences? How would that affect the time complexity?"

Practice

1. What does the PHP function preg_replace do?

easy

A. It splits a string into an array based on a pattern.

B. It counts how many times a pattern appears in a string.

C. It finds text matching a pattern and replaces it with new text.

D. It checks if a string matches a pattern and returns true or false.

Solution

1. Step 1: Understand the purpose of preg_replace

   The function preg_replace searches a string for parts that match a pattern and replaces those parts with new text.

2. Step 2: Compare with other functions

   Counting matches or splitting strings are done by other functions like preg_match_all or preg_split, not preg_replace.

3. Final Answer:

   It finds text matching a pattern and replaces it with new text. -> Option C

4. Quick Check:

   preg_replace replaces matched text [OK]

Hint: Remember: replace means find and change text [OK]

Common Mistakes:

• Confusing preg_replace with preg_match
• Thinking preg_replace counts matches
• Mixing preg_replace with string splitting functions

2. Which of the following is the correct syntax to replace all digits with '#' in PHP using preg_replace?

easy

A. preg_replace('/\D/', '#', $text);

B. preg_replace('/d/', '#', $text);

C. preg_replace('/[0-9]+/', '#', $text);

D. preg_replace('/\d/', '#', $text);

Solution

1. Step 1: Identify the pattern for digits

   The pattern '\d' matches any single digit (0-9). In PHP single-quoted strings, it is written as '/\d/'.

2. Step 2: Check other options

   B uses '/d/', which matches the literal letter 'd'. C uses '/[0-9]+/', which matches one or more consecutive digits, replacing the entire group with a single '#'. D uses '/\D/', which matches non-digits.

3. Final Answer:

   preg_replace('/\d/', '#', $text); -> Option D

4. Quick Check:

   Use '\d' to match digits [OK]

Hint: Use '\d' to match digits in regex [OK]

Common Mistakes:

• Forgetting to escape backslash in PHP strings
• Using 'd' instead of '\d' for digits
• Confusing '\d' with '\D' (non-digits)

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

$text = "Hello 123 World";
$result = preg_replace('/\d+/', 'NUM', $text);
echo $result;

medium

A. Hello NUM World

B. Hello 123 World

C. NUM NUM NUM World

D. Hello NUM123 World

Solution

1. Step 1: Understand the regex pattern '/\d+/'

   The pattern '\d+' matches one or more digits in a row. In the string, '123' matches this pattern.

2. Step 2: Apply preg_replace to the string

   The matched digits '123' are replaced by 'NUM'. So the string becomes 'Hello NUM World'.

3. Final Answer:

   Hello NUM World -> Option A

4. Quick Check:

   Digits replaced by 'NUM' = Hello NUM World [OK]

Hint: Look for digit groups replaced by 'NUM' [OK]

Common Mistakes:

• Thinking only single digits replaced separately
• Expecting original digits to remain
• Confusing pattern with non-digit matching

4. Identify the error in this PHP code snippet:

$text = "abc123def";
$result = preg_replace('/[a-z]/', 1, $text, 2);
echo $result;

medium

A. The limit parameter should be the third argument, not the fourth.

B. The replacement value must be a string, not an integer.

C. The pattern should be enclosed in double quotes, not single quotes.

D. preg_replace cannot limit replacements; the code is correct.

Solution

1. Step 1: Check preg_replace argument order

   The arguments are: pattern, replacement, subject, limit. The limit is correctly the fourth argument.

2. Step 2: Check replacement type

   The replacement should be a string. Using integer 1 will be converted to string '1' but is not recommended and can cause confusion.

3. Step 3: Check other options

   Pattern can be in single quotes. preg_replace supports limit parameter.

4. Final Answer:

   The replacement value must be a string, not an integer. -> Option B

5. Quick Check:

   Replacement should be string [OK]

Hint: Always use string for replacement in preg_replace [OK]

Common Mistakes:

• Passing integer instead of string as replacement
• Misplacing the limit parameter
• Thinking preg_replace can't limit replacements

5. You want to replace only the first two occurrences of the word 'apple' with 'orange' in the string 'apple banana apple apple grape'. Which preg_replace call achieves this?

hard

A. preg_replace('/apple/', 'orange', 'apple banana apple apple grape', 2);

B. preg_replace('/apple/', 'orange', 'apple banana apple apple grape');

C. preg_replace('/apple/', 'orange', 'apple banana apple apple grape', 3);

D. preg_replace('/apple/', 'orange', 'apple banana apple apple grape', 1);

Solution

1. Step 1: Understand the limit parameter in preg_replace

   The fourth argument limits how many replacements happen. To replace only first two 'apple', limit should be 2.

2. Step 2: Check each option's limit

   preg_replace('/apple/', 'orange', 'apple banana apple apple grape', 2); uses limit 2, so only first two 'apple' replaced. preg_replace('/apple/', 'orange', 'apple banana apple apple grape'); replaces all. preg_replace('/apple/', 'orange', 'apple banana apple apple grape', 3); replaces first three. preg_replace('/apple/', 'orange', 'apple banana apple apple grape', 1); replaces only first one.

3. Final Answer:

   preg_replace('/apple/', 'orange', 'apple banana apple apple grape', 2); -> Option A

4. Quick Check:

   Limit 2 replaces first two matches [OK]

Hint: Use limit parameter to control replacements count [OK]

Common Mistakes:

• Omitting limit to replace all occurrences
• Setting wrong limit number
• Confusing order of arguments