Capture groups in Ruby - Time & Space Complexity

Time Complexity: Capture groups

O(n)

Understanding Time Complexity

When using capture groups in Ruby regular expressions, it is important to understand how the time to find matches grows as the input string gets longer.

We want to know how the work done by the regex engine changes with bigger inputs.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

text = "abc123def456"
pattern = /(\d{3})/  # capture groups for 3 digits
matches = text.scan(pattern)
    

This code finds all groups of three digits in the text and stores them.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The regex engine scans through the input string character by character to find matches.
• How many times: It checks each position in the string once, trying to match the pattern with capture groups.

How Execution Grows With Input

As the input string gets longer, the regex engine does more checks, roughly one per character.

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 input size.

Final Time Complexity

Time Complexity: O(n)

This means the time to find capture groups grows linearly as the input string gets longer.

Common Mistake

[X] Wrong: "Capture groups make the regex run much slower, like exponentially slower."

[OK] Correct: Simple capture groups add only a small fixed amount of work per match attempt, so the overall time still grows linearly with input size.

Interview Connect

Understanding how capture groups affect regex performance helps you write efficient pattern matching code, a useful skill in many programming tasks.

Self-Check

"What if the pattern used nested capture groups or backreferences? How would the time complexity change?"

Practice

1. What does a capture group do in a Ruby regular expression like /(\d{3})-(\d{2})/?

easy

A. It repeats the pattern multiple times.

B. It saves parts of the matched text for later use.

C. It matches only digits without saving.

D. It ignores the matched text.

Solution

1. Step 1: Understand capture groups in regex

   Capture groups are parts of a pattern enclosed in parentheses that save matched text.

2. Step 2: Analyze the example pattern

   The pattern /(\d{3})-(\d{2})/ has two capture groups for three digits and two digits separated by a dash.

3. Final Answer:

   It saves parts of the matched text for later use. -> Option B

4. Quick Check:

   Capture groups = save matched parts [OK]

Hint: Parentheses in regex save matched text as groups [OK]

Common Mistakes:

• Thinking capture groups repeat patterns
• Confusing capture groups with non-capturing groups
• Believing capture groups ignore matched text

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

easy

A. /(abc)/

B. /[abc]/

C. /{abc}/

D. /abc/

Solution

1. Step 1: Identify capture group syntax

   Capture groups in Ruby regex are created by enclosing the pattern in parentheses ().

2. Step 2: Compare options

   /(abc)/ uses parentheses correctly. /[abc]/ uses square brackets which match any one character. /{abc}/ uses curly braces which are quantifiers. /abc/ has no capture group.

3. Final Answer:

   /(abc)/ -> Option A

4. Quick Check:

   Parentheses = capture group [OK]

Hint: Use parentheses () for capture groups in regex [OK]

Common Mistakes:

• Using square brackets [] instead of parentheses
• Using curly braces {} incorrectly
• Forgetting parentheses for capture groups

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

text = "Order 123-45"
match = text.match(/(\d{3})-(\d{2})/)
[match[0], match[1], match[2]]

medium

A. ["123-45", "45", "123"]

B. ["12345", "123", "45"]

C. ["Order 123-45", "123", "45"]

D. ["123-45", "123", "45"]

Solution

1. Step 1: Understand match and capture groups

   The match method returns a MatchData object. match[0] is the full matched string, match[1] and match[2] are the first and second capture groups.

2. Step 2: Apply to given string and pattern

   The pattern matches "123-45" in the text. The first group captures "123", the second "45".

3. Final Answer:

   ["123-45", "123", "45"] -> Option D

4. Quick Check:

   Full match + groups = ["123-45", "123", "45"] [OK]

Hint: match[0] full, match[1..] capture groups [OK]

Common Mistakes:

• Confusing full match with capture groups
• Swapping capture group order
• Ignoring the dash in the match

4. What is wrong with this Ruby code snippet?

text = "abc123"
match = text.match(/(\d{3})/)
puts match[1]

medium

A. It prints "123" correctly.

B. It raises an error because there is no match.

C. It prints nil without error.

D. It raises a syntax error.

Solution

1. Step 1: Check the regex and string

   The regex /(\d{3})/ looks for exactly three digits. The string "abc123" contains "123" which matches.

2. Step 2: Understand match and output

   The match object captures "123" in group 1. puts match[1] prints "123".

3. Final Answer:

   It prints "123" correctly. -> Option A

4. Quick Check:

   Digits found and printed = "123" [OK]

Hint: Check if regex matches before accessing groups [OK]

Common Mistakes:

• Assuming no match causes error
• Expecting nil instead of matched string
• Confusing syntax error with runtime error

5. Given a string of dates like "2023-04-01, 2024-12-31", which Ruby code correctly extracts all year parts using capture groups?

hard

A. dates.scan(/\d{4}-\d{2}-\d{2}/)

B. dates.match(/(\d{4})-\d{2}-\d{2}/)

C. dates.scan(/(\d{4})-\d{2}-\d{2}/).flatten

D. dates.match(/\d{4}/)

Solution

1. Step 1: Understand the goal and methods

   We want all years from multiple dates. scan finds all matches, match finds only first.

2. Step 2: Analyze each option

   dates.scan(/(\d{4})-\d{2}-\d{2}/).flatten uses scan with a capture group for year, returning all years as array. dates.match(/(\d{4})-\d{2}-\d{2}/) uses match which returns only first match. dates.scan(/\d{4}-\d{2}-\d{2}/) uses scan but no capture group, returns full dates. dates.match(/\d{4}/) uses match without capture group, only first year.

3. Final Answer:

   dates.scan(/(\d{4})-\d{2}-\d{2}/).flatten -> Option C

4. Quick Check:

   scan + capture group = all years [OK]

Hint: Use scan with capture groups to get all matches [OK]

Common Mistakes:

• Using match instead of scan for multiple matches
• Not using capture groups to extract parts
• Forgetting to flatten nested arrays from scan