Preg_match for pattern matching in PHP - Time & Space Complexity

Time Complexity: Preg_match for pattern matching

O(n)

Understanding Time Complexity

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

We want to understand how the pattern matching works scales with input size.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

$string = "Hello, this is a sample text.";
$pattern = '/sample/';
if (preg_match($pattern, $string)) {
    echo "Match found!";
} else {
    echo "No match.";
}
    

This code checks if the word "sample" appears anywhere in the given string.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The pattern matcher scans through the input string character by character.
• How many times: Up to once per character in the string, depending on the pattern and input.

How Execution Grows With Input

The time to check the pattern grows roughly in proportion to the length of the input string.

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

Pattern observation: As the string gets longer, the work grows roughly in a straight line with the input size.

Final Time Complexity

Time Complexity: O(n)

This means the time to find a match grows linearly with the length of the input string.

Common Mistake

[X] Wrong: "preg_match always runs instantly no matter the input size."

[OK] Correct: The function must check characters one by one, so longer strings take more time.

Interview Connect

Understanding how pattern matching scales helps you write efficient code and explain your choices clearly in interviews.

Self-Check

"What if the pattern uses complex wildcards or backreferences? How would the time complexity change?"

Practice

1. What does the PHP function preg_match return when the pattern is found in the string?

easy

A. 1

B. 0

C. true

D. false

Solution

1. Step 1: Understand preg_match return values

   The function preg_match returns 1 if the pattern matches the string.

2. Step 2: Differentiate from no match

   If the pattern is not found, it returns 0, not true or false.

3. Final Answer:

   1 -> Option A

4. Quick Check:

   preg_match returns 1 if pattern found [OK]

Hint: Remember: preg_match returns 1 for match, 0 for no match [OK]

Common Mistakes:

• Confusing return values with boolean true/false
• Assuming preg_match returns the matched string
• Thinking preg_match returns number of matches

2. Which of the following is the correct syntax to check if the string $text contains the word "hello" using preg_match?

easy

A. preg_match('hello', $text);

B. preg_match('/hello/', $text);

C. preg_match(/hello/, $text);

D. preg_match("/hello", $text);

Solution

1. Step 1: Identify correct pattern delimiters

   Patterns in preg_match must be enclosed in quotes and slashes, like '/pattern/'.

2. Step 2: Check each option's syntax

   preg_match('/hello/', $text); uses quotes and slashes correctly. preg_match('hello', $text); misses slashes. preg_match(/hello/, $text); misses quotes. preg_match("/hello", $text); misses closing slash.

3. Final Answer:

   preg_match('/hello/', $text); -> Option B

4. Quick Check:

   Pattern must be in quotes with slashes [OK]

Hint: Use quotes and slashes around pattern in preg_match [OK]

Common Mistakes:

• Omitting quotes around the pattern
• Omitting slashes around the pattern
• Using wrong quote types inconsistently

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

$text = "apple123";
if (preg_match('/\d+/', $text)) {
    echo "Digits found";
} else {
    echo "No digits";
}

medium

A. Syntax error

B. No digits

C. Digits found

D. Empty output

Solution

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

   The pattern \d+ matches one or more digits in the string.

2. Step 2: Check if $text contains digits

   The string "apple123" contains digits "123", so preg_match returns 1 and the if condition is true.

3. Final Answer:

   Digits found -> Option C

4. Quick Check:

   Pattern \d+ matches digits, output is 'Digits found' [OK]

Hint: \d+ matches digits; check string for numbers [OK]

Common Mistakes:

• Not escaping backslash properly in pattern
• Assuming preg_match returns matched string
• Confusing preg_match return with boolean true/false

4. The following code is intended to check if a string contains only letters. What is wrong with it?

$str = "Hello123";
if (preg_match('/^[a-zA-Z]+$/', $str)) {
    echo "Only letters";
} else {
    echo "Contains other characters";
}

medium

A. The pattern is correct but the string contains digits

B. Missing delimiters around the pattern

C. The pattern should use \w instead of [a-zA-Z]

D. preg_match should be preg_match_all

Solution

1. Step 1: Analyze the pattern and string

   The pattern '/^[a-zA-Z]+$/' matches strings with only letters from start to end. The string "Hello123" contains digits, so it does not match.

2. Step 2: Identify the actual problem

   The pattern is correct, but the string has digits, so the else branch runs.

3. Final Answer:

   The pattern is correct but the string contains digits -> Option A

4. Quick Check:

   Pattern matches only letters; digits cause no match [OK]

Hint: Check if string matches pattern exactly, not just pattern syntax [OK]

Common Mistakes:

• Thinking pattern is wrong when string is the issue
• Confusing preg_match with preg_match_all
• Removing anchors ^ and $ incorrectly

5. You want to check if a string contains a valid email address using preg_match. Which pattern correctly matches a simple email format like '[e-mail]'?

hard

A. '/^[a-z]+@[a-z]+\.[a-z]{2,3}$/'

B. '/^[\d]+@[\d]+\.[\d]{2,4}$/'

C. '/\w+@\w+\.com/'

D. '/^[\w.-]+@[\w.-]+\.[a-zA-Z]{2,6}$/'

Solution

1. Step 1: Understand email pattern requirements

   A simple email has letters, digits, dots, or dashes before and after '@', then a dot and 2-6 letter domain.

2. Step 2: Evaluate each pattern

   '/^[\w.-]+@[\w.-]+\.[a-zA-Z]{2,6}$/' matches letters, digits, dots, dashes before and after '@', and domain with 2-6 letters. '/^[a-z]+@[a-z]+\.[a-z]{2,3}$/' is too restrictive (only lowercase letters, domain 2-3 letters). '/\w+@\w+\.com/' matches only '.com' domains and misses anchors. '/^[\d]+@[\d]+\.[\d]{2,4}$/' matches digits only, which is invalid for emails.

3. Final Answer:

   '/^[\w.-]+@[\w.-]+\.[a-zA-Z]{2,6}$/' -> Option D

4. Quick Check:

   '/^[\w.-]+@[\w.-]+\.[a-zA-Z]{2,6}$/' matches common email format correctly [OK]

Hint: Use \w, dots, dashes, and domain length for email pattern [OK]

Common Mistakes:

• Not using anchors ^ and $ to match whole string
• Restricting domain or username too much
• Ignoring dots and dashes in username or domain