Named captures in Ruby - Time & Space Complexity

Time Complexity: Named captures

O(n)

Understanding Time Complexity

We want to understand how the time it takes to find named parts in text grows as the text gets longer.

How does the work change when we use named captures in Ruby regular expressions?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

text = "Name: John, Age: 30; Name: Jane, Age: 25"
pattern = /Name: (?\w+), Age: (?\d+)/

text.scan(pattern) do
  name = Regexp.last_match[:name]
  age = Regexp.last_match[:age]
  # process name and age
end
    

This code finds all name and age pairs in a string using named captures in a regular expression.

Identify Repeating Operations

• Primary operation: The scan method loops through the text to find matches.
• How many times: It runs once for each match found in the text.

How Execution Grows With Input

As the text gets longer, the number of matches usually grows too, so the work grows with the text size.

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

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

Final Time Complexity

Time Complexity: O(n)

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

Common Mistake

[X] Wrong: "Using named captures makes the search slower by a lot."

[OK] Correct: Named captures add only a small, constant amount of work per match, so the overall time still grows mainly with the text size.

Interview Connect

Understanding how pattern matching scales helps you write efficient text processing code, a useful skill in many programming tasks.

Self-Check

"What if we changed the pattern to use unnamed captures instead? How would the time complexity change?"

Practice

1. What does a named capture group in Ruby regex do?
/(?<name>pattern)/

easy

A. Repeats the pattern multiple times

B. Makes the regex case-insensitive

C. Labels a part of the matched text with a name for easy access

D. Matches only digits in the text

Solution

1. Step 1: Understand named capture syntax

   The syntax ?<name> inside parentheses names the capture group.

2. Step 2: Purpose of named captures

   This lets you access matched parts by name instead of number, making code clearer.

3. Final Answer:

   Labels a part of the matched text with a name for easy access -> Option C

4. Quick Check:

   Named capture = label matched text [OK]

Hint: Named captures label groups for easy access by name [OK]

Common Mistakes:

• Confusing named captures with regex flags
• Thinking named captures repeat patterns
• Assuming named captures only match digits

2. Which of the following is the correct syntax for a named capture group in Ruby regex?

easy

A. /<year>\d{4}/

B. /(?year>\d{4})/

C. /(?/

D. /(?<year>\d{4})/

Solution

1. Step 1: Recall named capture syntax

   Named captures use ?<name> inside parentheses to name the group.

2. Step 2: Check each option

   /(?<year>\d{4})/ correctly uses (?<year>\d{4}). Others miss brackets or have wrong syntax.

3. Final Answer:

   /(?<year>\d{4})/ is correct syntax -> Option D

4. Quick Check:

   Correct syntax = (?<name>) [OK]

Hint: Look for parentheses with ?<name> inside [OK]

Common Mistakes:

• Omitting angle brackets around the name
• Placing name outside parentheses
• Using wrong brackets or missing parentheses

3. What is the output of this Ruby code?

text = "Date: 2024-06-15"
regex = /(?<year>\d{4})-(?<month>\d{2})-(?<day>\d{2})/
m = text.match(regex)
puts "Year: #{m[:year]}, Month: #{m[:month]}, Day: #{m[:day]}"

medium

A. Year: 2024, Month: 06, Day: 15

B. Year: , Month: , Day:

C. Year: 2024-06-15, Month: 2024-06-15, Day: 2024-06-15

D. Error: undefined method [] for nil

Solution

1. Step 1: Match regex with named captures

   The regex captures year, month, and day parts from the text "Date: 2024-06-15".

2. Step 2: Access named captures from match object

   Using m[:year], m[:month], and m[:day] returns "2024", "06", and "15" respectively.

3. Final Answer:

   Year: 2024, Month: 06, Day: 15 -> Option A

4. Quick Check:

   Named captures return parts by name [OK]

Hint: Use m[:name] to get named capture values [OK]

Common Mistakes:

• Using m['name'] instead of m[:name]
• Forgetting to call match before accessing captures
• Expecting full match instead of named parts

4. Find the error in this Ruby code using named captures:

text = "User: alice, Age: 30"
regex = /User: (?<name>\w+), Age: (?<age>\d+)/
m = regex.match(text)
puts "Name: #{m['name']}, Age: #{m['age']}"

medium

A. Regex pattern missing parentheses

B. Using string keys instead of symbols to access named captures

C. Match method called on regex instead of string

D. No error, code runs fine

Solution

1. Step 1: Check how named captures are accessed

   Named captures in Ruby match objects are accessed with symbols, like m[:name], not strings.

2. Step 2: Identify the error in code

   The code uses m['name'] and m['age'], which causes a nil result or error.

3. Final Answer:

   Using string keys instead of symbols to access named captures -> Option B

4. Quick Check:

   Use symbols, not strings, for named captures [OK]

Hint: Access named captures with symbols like m[:name] [OK]

Common Mistakes:

• Using string keys instead of symbols
• Confusing match method call on regex vs string
• Missing parentheses in regex groups

5. Given this text:

"Order #1234: 5 items, total $99.95"

Write a Ruby regex with named captures to extract order number, item count, and total price.
Which regex correctly captures these parts?

hard

A. /Order #(?<order_num>\d+): (?<items>\d+) items, total \$(?<total>\d+\.\d{2})/

B. /Order #(?<order_num>\d+), (?<items>\d+) items total \$(?<total>\d+\.\d{2})/

C. /Order #(?<order_num>\d+): (?<items>\d+) items total \$(?<total>\d+\.\d{2})/

D. /Order #(?<order_num>\d+): (?<items>\d+) items, total \$(?<total>\d+\.\d{3})/

Solution

1. Step 1: Analyze the text format

   The text is "Order #1234: 5 items, total $99.95" with colon and comma exactly as shown.

2. Step 2: Match regex parts carefully

   /Order #(?<order_num>\d+): (?<items>\d+) items, total \$(?<total>\d+\.\d{2})/ matches colon after order number, space, number of items, comma, space, "total $", and price with two decimals.

3. Step 3: Check other options

   Options A and C miss the comma or colon or both, and /Order #(?<order_num>\d+): (?<items>\d+) items, total \$(?<total>\d+\.\d{3})/ expects three decimals instead of two.

4. Final Answer:

   /Order #(?<order_num>\d+): (?<items>\d+) items, total \$(?<total>\d+\.\d{2})/ -> Option A

5. Quick Check:

   Match exact punctuation and decimal places [OK]

Hint: Match exact punctuation and decimal digits in regex [OK]

Common Mistakes:

• Missing colon or comma in pattern
• Wrong decimal places in price capture
• Using incorrect group names or syntax