Common patterns and character classes in Ruby - Time & Space Complexity

Time Complexity: Common patterns and character classes

O(n)

Understanding Time Complexity

When using common patterns and character classes in Ruby regular expressions, it's important to understand how the matching process scales as the input grows.

We want to know how the time to find matches changes when the text gets longer.

Scenario Under Consideration

Analyze the time complexity of the following Ruby code snippet.

text = "a1b2c3d4e5"
pattern = /[a-z]\d/
matches = text.scan(pattern)
puts matches
    

This code finds all pairs where a lowercase letter is followed by a digit in the given text.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The scan method checks each position in the text to see if the pattern matches starting there.
• How many times: It tries matching at every character index, so roughly once per character in the text.

How Execution Grows With Input

As the text gets longer, the number of checks grows roughly in direct proportion to the text length.

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 input grows, roughly one check per character.

Final Time Complexity

Time Complexity: O(n)

This means the time to find matches grows in a straight line with the size of the input text.

Common Mistake

[X] Wrong: "Using character classes makes the search instant regardless of input size."

[OK] Correct: Even with character classes, the program still checks each position in the text, so time grows with input length.

Interview Connect

Understanding how pattern matching scales helps you write efficient code and explain your reasoning clearly in interviews.

Self-Check

"What if the pattern included a quantifier like + or *? How would the time complexity change?"

Practice

1. Which Ruby regular expression pattern matches any single digit character?

easy

A. /\D/

B. /\d/

C. /\s/

D. /\w/

Solution

1. Step 1: Understand \d in Ruby regex

   The pattern \d matches any digit character (0-9).

2. Step 2: Compare with other options

   \w matches word characters (letters, digits, underscore), \s matches whitespace, \D matches non-digit characters.

3. Final Answer:

   /\d/ -> Option B

4. Quick Check:

   Digit pattern = /\d/ [OK]

Hint: Remember \d means digit, \w means word character [OK]

Common Mistakes:

• Confusing \d with \w
• Using /\D/ which matches non-digits
• Thinking \s matches digits

2. Which of the following is the correct Ruby syntax to match any word character one or more times?

easy

A. /\w+/

B. /\w*/

C. /\w?/

D. /\w{}/

Solution

1. Step 1: Understand quantifiers in regex

   + means one or more times, * means zero or more, ? means zero or one.

2. Step 2: Apply to \w

   /\w+/ matches one or more word characters, which is the correct syntax.

3. Final Answer:

   /\w+/ -> Option A

4. Quick Check:

   One or more word chars = /\w+/ [OK]

Hint: Use + for one or more matches in regex [OK]

Common Mistakes:

• Using * which allows zero matches
• Using ? which allows zero or one match
• Using empty braces {} which is invalid

3. What is the output of this Ruby code?

text = "Room 101"
match = text.match(/\d+/)
puts match[0]

medium

A. 101

B. Room

C. 1

D. nil

Solution

1. Step 1: Understand the regex /\d+/

   This pattern matches one or more digits in a row.

2. Step 2: Apply match to string "Room 101"

   The digits "101" are matched as a group, so match[0] returns "101".

3. Final Answer:

   101 -> Option A

4. Quick Check:

   Digits matched = 101 [OK]

Hint: \d+ grabs all digits in a row, not just one [OK]

Common Mistakes:

• Thinking it matches only one digit
• Confusing match[0] with match object
• Expecting the word part instead of digits

4. Find the error in this Ruby code snippet:

email = "[e-mail]"
if email =~ /\w+@\w+.\w+/
  puts "Valid email"
else
  puts "Invalid email"
end

medium

A. The regex should use \d instead of \w

B. The =~ operator is used incorrectly

C. The regex does not escape the dot properly

D. The string should be in single quotes

Solution

1. Step 1: Examine the regex pattern

   The pattern /\w+@\w+.\w+/ uses an unescaped . which matches any character, not a literal dot.

2. Step 2: Identify the error

   The dot after the domain must be escaped as \. to match the literal "." in email addresses.

3. Final Answer:

   The regex does not escape the dot properly -> Option C

4. Quick Check:

   Escape literal dot as \. [OK]

Hint: Remember to escape dot as \. to match literal dot [OK]

Common Mistakes:

• Thinking dot doesn't need escaping
• Misusing =~ operator
• Confusing \w with \d in email regex

5. You want to extract all words starting with a capital letter from the string "Hello World from Ruby". Which Ruby regex pattern should you use with scan?

hard

A. /\d+/

B. /\b[a-z]\w*/

C. /\s+/

D. /\b[A-Z]\w*/

Solution

1. Step 1: Understand the requirement

   We want words starting with a capital letter, so first letter must be A-Z.

2. Step 2: Analyze the regex options

   /\b[A-Z]\w*/ matches word boundary, then capital letter, then zero or more word chars.

3. Step 3: Check other options

   /\b[a-z]\w*/ matches lowercase start, /\d+/ matches digits, /\s+/ matches spaces, so they don't fit.

4. Final Answer:

   /\b[A-Z]\w*/ -> Option D

5. Quick Check:

   Capital-start words = /\b[A-Z]\w*/ [OK]

Hint: Use \b for word boundary and [A-Z] for capital letters [OK]

Common Mistakes:

• Using [a-z] instead of [A-Z]
• Forgetting word boundary \b
• Using digit or space patterns incorrectly