Regex literal syntax (/pattern/) in Ruby - Time & Space Complexity

Time Complexity: Regex literal syntax (/pattern/)

O(n)

Understanding Time Complexity

We want to understand how the time it takes to use a regex pattern changes as the input grows.

How does matching a pattern scale when the text gets longer?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

text = "hello world" * n
pattern = /world/
result = text.match(pattern)

This code checks if the word "world" appears in a long repeated text string.

Identify Repeating Operations

Look at what repeats when matching the pattern.

• Primary operation: The regex engine scans the text characters one by one to find the pattern.
• How many times: Up to once per character in the text, depending on where the pattern is found.

How Execution Grows With Input

As the text gets longer, the regex engine checks more characters.

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

Pattern observation: The work grows roughly in direct proportion to the text length.

Final Time Complexity

Time Complexity: O(n)

This means the time to find the pattern grows linearly as the text gets longer.

Common Mistake

[X] Wrong: "Regex matching always takes the same time no matter the text size."

[OK] Correct: The regex engine usually checks each character, so longer text means more work.

Interview Connect

Understanding how regex matching scales helps you write efficient code and explain your choices clearly.

Self-Check

"What if the pattern was more complex with repetitions or optional parts? How would that affect the time complexity?"

Practice

1. What is the correct way to write a regex literal in Ruby to match the word cat?

easy

A. regex('cat')

B. "cat"

C. 'cat'

D. /cat/

Solution

1. Step 1: Understand regex literal syntax

   In Ruby, regex literals are written between slashes, like /pattern/.

2. Step 2: Identify the correct pattern for 'cat'

   The pattern to match the word 'cat' is simply /cat/.

3. Final Answer:

   /cat/ -> Option D

4. Quick Check:

   Regex literal = /pattern/ [OK]

Hint: Regex literals always use slashes /pattern/ in Ruby [OK]

Common Mistakes:

• Using quotes instead of slashes
• Calling a non-existent regex() function
• Confusing string and regex syntax

2. Which of the following is the correct regex literal to match the word Dog case-insensitively in Ruby?

easy

A. /Dog/m

B. /Dog/g

C. /Dog/i

D. /Dog/

Solution

1. Step 1: Identify the case-insensitive option

   In Ruby regex, the i option after the slashes makes matching case-insensitive.

2. Step 2: Check the options given

   Only /Dog/i uses the correct i flag for case-insensitive matching.

3. Final Answer:

   /Dog/i -> Option C

4. Quick Check:

   Case-insensitive flag = i [OK]

Hint: Use /pattern/i for case-insensitive regex in Ruby [OK]

Common Mistakes:

• Using g or m flags which mean different things
• Omitting the i flag for case-insensitivity
• Placing flags inside the slashes

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

text = "Hello World"
match = text =~ /world/i
puts match

medium

A. nil

B. 6

C. 0

D. Error

Solution

1. Step 1: Understand the =~ operator with regex

   The operator =~ returns the index of the first match or nil if no match.

2. Step 2: Analyze the regex and string

   The regex /world/i matches 'World' ignoring case. In "Hello World", 'World' starts at index 6 (0-based).

3. Final Answer:

   6 -> Option B

4. Quick Check:

   Case-insensitive match index = 6 [OK]

Hint: =~ returns match start index or nil if no match [OK]

Common Mistakes:

• Ignoring case-insensitive flag i
• Thinking output is true/false instead of index
• Assuming match starts at 0 always

4. Identify the error in this Ruby regex literal:

pattern = /hello/i/

medium

A. Extra slash at the end causes syntax error

B. Missing quotes around pattern

C. Missing i flag for case-insensitivity

D. Regex literals cannot have flags

Solution

1. Step 1: Check regex literal syntax

   A regex literal starts and ends with a single slash. Here, there is an extra slash at the end.

2. Step 2: Identify the syntax error

   The extra slash after /hello/i is invalid and causes a syntax error.

3. Final Answer:

   Extra slash at the end causes syntax error -> Option A

4. Quick Check:

   Regex literal must start and end with one slash pair [OK]

Hint: Regex literals have exactly two slashes, no extras [OK]

Common Mistakes:

• Adding extra slash after regex
• Confusing regex with string quotes
• Thinking flags go inside slashes

5. You want to find all words starting with a or A in a string using a regex literal. Which regex literal correctly matches this requirement?

hard

A. /\b[a]\w*/i

B. /\b[A]\w*/

C. /\b[a]\w*/

D. /\b[a-z]\w*/i

Solution

1. Step 1: Understand the requirement

   We want words starting with 'a' or 'A'. Using case-insensitive flag i simplifies matching both.

2. Step 2: Analyze options

   /\b[a]\w*/i uses /\b[a]\w*/i which matches word boundary, then 'a' (case-insensitive), then zero or more word chars. This matches words starting with 'a' or 'A'.

3. Final Answer:

   /\b[a]\w*/i -> Option A

4. Quick Check:

   Use i flag to match both 'a' and 'A' easily [OK]

Hint: Use /pattern/i to match letters ignoring case [OK]

Common Mistakes:

• Listing both 'a' and 'A' inside brackets without i flag
• Using wrong character classes
• Missing word boundary \b