Scan for all matches in Ruby - Time & Space Complexity

Time Complexity: Scan for all matches

O(n)

Understanding Time Complexity

We want to understand how long it takes to find all matches of a pattern in a string.

How does the time needed grow as the string gets longer?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

text = "hello hello hello"
pattern = /hello/
matches = text.scan(pattern)

This code finds all occurrences of "hello" in the text string.

Identify Repeating Operations

• Primary operation: The scan method checks each position in the string to see if the pattern matches.
• How many times: It repeats this check for almost every character in the string.

How Execution Grows With Input

As the string gets longer, the number of checks grows roughly in direct proportion.

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

Pattern observation: The work grows steadily as the string grows longer.

Final Time Complexity

Time Complexity: O(n)

This means the time to find all matches grows in a straight line with the string length.

Common Mistake

[X] Wrong: "The scan method only looks at the first few characters, so it's very fast regardless of string size."

[OK] Correct: Actually, scan checks the whole string to find all matches, so the time grows with the string length.

Interview Connect

Understanding how searching through text grows with input size helps you explain efficiency clearly and confidently.

Self-Check

"What if the pattern was more complex, like a nested group or optional parts? How would the time complexity change?"

Practice

1. What does the Ruby method scan do when used on a string?

easy

A. It counts the number of characters in the string.

B. It replaces all matches of a pattern with another string.

C. It finds all matches of a pattern and returns them in an array.

D. It converts the string to uppercase.

Solution

1. Step 1: Understand the purpose of scan

   The scan method searches the string for all occurrences of a pattern.

2. Step 2: Identify the return value of scan

   It returns an array containing all matched parts of the string.

3. Final Answer:

   It finds all matches of a pattern and returns them in an array. -> Option C

4. Quick Check:

   scan returns matches array [OK]

Hint: Remember: scan returns all matches as an array [OK]

Common Mistakes:

• Confusing scan with gsub (replacement)
• Thinking scan returns a count
• Assuming scan modifies the original string

2. Which of the following is the correct syntax to find all digits in a string str using scan?

easy

A. str.scan(/d+)

B. str.scan("\\d+")

C. str.scan('\d+')

D. str.scan(/\d+/)

Solution

1. Step 1: Recognize the correct regex syntax in Ruby

   Ruby uses forward slashes /pattern/ to denote regular expressions.

2. Step 2: Identify the correct regex for digits

   \d+ matches one or more digits. The pattern must be inside slashes for regex.

3. Final Answer:

   str.scan(/\d+/) -> Option D

4. Quick Check:

   Regex in slashes with \d+ = str.scan(/\d+/) [OK]

Hint: Use /pattern/ for regex, not strings, in scan [OK]

Common Mistakes:

• Using string quotes instead of regex slashes
• Missing escape backslash in regex
• Using incorrect regex delimiters

3. What is the output of the following Ruby code?

text = "cat bat rat"
matches = text.scan(/.at/)
puts matches.inspect

medium

A. ["at", "at", "at"]

B. ["cat", "bat", "rat"]

C. ["c", "b", "r"]

D. []

Solution

1. Step 1: Understand the regex /.at/

   The dot . matches any single character, so .at matches any three-letter word ending with 'at'.

2. Step 2: Apply scan on the string

   The string "cat bat rat" contains "cat", "bat", and "rat" which all match the pattern.

3. Final Answer:

   ["cat", "bat", "rat"] -> Option B

4. Quick Check:

   scan finds all 3-letter words ending with 'at' [OK]

Hint: Dot matches any char; scan returns all full matches [OK]

Common Mistakes:

• Thinking dot matches zero or multiple chars
• Expecting partial matches like 'at' only
• Confusing scan output with string split

4. The following code is intended to find all words starting with 'a' in sentence. What is the error?

sentence = "apple banana apricot avocado"
words = sentence.scan("a\w+")
puts words.inspect

medium

A. The pattern should be a regex, not a string.

B. The pattern should use double backslashes.

C. The method scan does not work on strings.

D. The variable name 'words' is invalid.

Solution

1. Step 1: Check the argument type for scan

   The scan method expects a regex pattern, not a plain string.

2. Step 2: Identify correct regex usage

   The pattern should be written as /a\w+/ to match words starting with 'a'.

3. Final Answer:

   The pattern should be a regex, not a string. -> Option A

4. Quick Check:

   scan requires regex pattern, not string [OK]

Hint: Use /pattern/ for regex in scan, not string quotes [OK]

Common Mistakes:

• Passing string instead of regex to scan
• Misunderstanding backslash escaping
• Assuming scan modifies the string

5. Given the string data = "log12 ID123, ID456, ID789", how can you use scan to extract only the numeric parts after each 'ID' (e.g., ["123", "456", "789"])?

hard

A. data.scan(/ID(\d+)/).flatten

B. data.scan(/\d+/)

C. data.scan(/ID\d+/)

D. data.scan(/(ID\d+)/)

Solution

1. Step 1: Understand the pattern to extract numbers after 'ID'

   The regex /ID(\d+)/ matches 'ID' followed by digits, capturing only digits in parentheses. This ignores other digits like '12' in 'log12'.

2. Step 2: Use scan and flatten the result

   scan returns an array of arrays for capture groups, so flatten converts it to a simple array of strings.

3. Final Answer:

   data.scan(/ID(\d+)/).flatten -> Option A

4. Quick Check:

   Capture group extracts digits, flatten simplifies array [OK]

Hint: Use capture groups and flatten to get inner matches [OK]

Common Mistakes:

• Using data.scan(/\d+/) which grabs all digits including extras like '12' and '78'
• Using scan without flatten, getting nested arrays
• Matching full 'ID123' instead of just digits