Match method and MatchData in Ruby - Time & Space Complexity

Time Complexity: Match method and MatchData

O(n)

Understanding Time Complexity

We want to understand how long it takes for Ruby's match method to find a pattern in a string.

How does the time needed grow when the string gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

text = "hello world"
pattern = /world/
result = text.match(pattern)
if result
  puts "Found: #{result[0]}"
else
  puts "Not found"
end
    

This code tries to find the word "world" inside the string "hello world" using the match method.

Identify Repeating Operations

Look for parts that repeat or check many characters.

• Primary operation: Checking each character in the string to see if the pattern fits.
• How many times: Up to once for each character in the string, until the pattern is found or the string ends.

How Execution Grows With Input

As the string gets longer, the method checks more characters.

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

Pattern observation: The number of checks grows roughly the same as the string length.

Final Time Complexity

Time Complexity: O(n)

This means the time to find the pattern grows in a straight line with the string size.

Common Mistake

[X] Wrong: "The match method always takes the same time no matter the string size."

[OK] Correct: The method checks characters one by one, so longer strings usually take more time.

Interview Connect

Understanding how pattern matching grows with input size helps you explain how your code handles bigger data smoothly.

Self-Check

"What if the pattern was a more complex regular expression? How would that affect the time complexity?"

Practice

1. What does the Ruby match method return when it finds a pattern in a string?

easy

A. A MatchData object containing details of the match

B. The matched substring as a string

C. An array of all matched substrings

D. A boolean value true

Solution

1. Step 1: Understand the purpose of match

   The match method searches a string for a pattern and returns information about the match.

2. Step 2: Identify the return type when a match is found

   It returns a MatchData object, which holds details like matched text and position.

3. Final Answer:

   A MatchData object containing details of the match -> Option A

4. Quick Check:

   match returns MatchData [OK]

Hint: Remember: match returns MatchData, not just string [OK]

Common Mistakes:

• Thinking it returns just the matched string
• Assuming it returns an array of matches
• Believing it returns true/false

2. Which of the following is the correct syntax to use the match method on a string str to find the pattern /abc/?

easy

A. /abc/.match(str)

B. match(str, /abc/)

C. str.match(/abc/)

D. str.match = /abc/

Solution

1. Step 1: Recall the method call format

   The match method is called on a string object with a regex pattern as argument.

2. Step 2: Check each option's syntax

   str.match(/abc/) correctly calls str.match(/abc/). match(str, /abc/) is invalid syntax. /abc/.match(str) reverses receiver and argument. str.match = /abc/ tries assignment, which is wrong.

3. Final Answer:

   str.match(/abc/) -> Option C

4. Quick Check:

   Correct method call = str.match(/abc/) [OK]

Hint: Call match on string with regex inside parentheses [OK]

Common Mistakes:

• Using match as a standalone function
• Swapping receiver and argument
• Trying to assign with =

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

result = "hello123".match(/\d+/)
puts result[0]

medium

A. 123

B. hello

C. nil

D. An error is raised

Solution

1. Step 1: Understand the regex pattern

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

2. Step 2: Analyze the match and output

   In "hello123", digits "123" match. result[0] accesses the matched substring "123".

3. Final Answer:

   123 -> Option A

4. Quick Check:

   Digits matched = "123" [OK]

Hint: Access matched text with result[0] after match [OK]

Common Mistakes:

• Expecting the whole string as output
• Confusing nil with empty string
• Not using index 0 to get matched text

4. Consider this Ruby code snippet:

text = "abc"
match = text.match(/d/)
puts match[0]

What is the problem here?

medium

A. The regex pattern is invalid

B. Trying to access match[0] when match is nil

C. The string text is empty

D. The match method does not exist for strings

Solution

1. Step 1: Check the regex pattern and string

   The pattern /d/ looks for 'd' in "abc", which is not present, so match returns nil.

2. Step 2: Identify the error cause

   Trying to do match[0] when match is nil causes a NoMethodError.

3. Final Answer:

   Trying to access match[0] when match is nil -> Option B

4. Quick Check:

   Accessing [0] on nil causes error [OK]

Hint: Check if match is nil before accessing [OK]

Common Mistakes:

• Assuming pattern is invalid
• Ignoring that match can be nil
• Thinking match method is missing

5. You want to extract the first word starting with a capital letter from the string "today is a Sunny day" using match. Which code correctly does this and prints the matched word?

hard

A. puts "today is a Sunny day".match(/[A-Z]+/)[0]

B. puts "today is a Sunny day".match(/[a-z]\w*/)[0]

C. puts "today is a Sunny day".match(/\b\w+/)[0]

D. puts "today is a Sunny day".match(/[A-Z]\w*/)[0]

Solution

1. Step 1: Understand the regex requirements

   We want the first word starting with a capital letter. Pattern /[A-Z]\w*/ matches a capital letter followed by zero or more word characters.

2. Step 2: Analyze each option

   puts "today is a Sunny day".match(/[A-Z]\w*/)[0] matches correctly and returns the first capitalized word "Sunny". puts "today is a Sunny day".match(/[a-z]\w*/)[0] matches lowercase start, first is "today", wrong. puts "today is a Sunny day".match(/\b\w+/)[0] matches any word, first is "today", not capitalized. puts "today is a Sunny day".match(/[A-Z]+/)[0] matches only consecutive capital letters, first is "S", not full word.

3. Final Answer:

   puts "today is a Sunny day".match(/[A-Z]\w*/)[0] -> Option D

4. Quick Check:

   Capitalized word match = puts "today is a Sunny day".match(/[A-Z]\w*/)[0] [OK]

Hint: Use regex starting with [A-Z] and access [0] from match [OK]

Common Mistakes:

• Using lowercase letter class instead of uppercase
• Matching only letters without full word
• Not accessing matched text with [0]