Gsub with regex in Ruby - Time & Space Complexity

Time Complexity: Gsub with regex

O(n)

Understanding Time Complexity

When using gsub with a regular expression in Ruby, it's important to understand how the time taken grows as the input string gets longer.

We want to know how the number of operations changes when the string size increases.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

text = "hello world hello"
pattern = /hello/
result = text.gsub(pattern, "hi")
puts result
    

This code replaces all occurrences of "hello" with "hi" in the given text string.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Scanning the entire string to find matches for the regex pattern.
• How many times: Each character in the string is checked once or a few times depending on the regex engine.

How Execution Grows With Input

As the input string gets longer, the time to scan and replace grows roughly in direct proportion to the string 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 string gets longer, roughly one check per character.

Final Time Complexity

Time Complexity: O(n)

This means the time to complete the replacement grows in a straight line with the length of the input string.

Common Mistake

[X] Wrong: "Using regex with gsub always takes the same time no matter how long the string is."

[OK] Correct: The regex engine must check each part of the string to find matches, so longer strings take more time.

Interview Connect

Understanding how string operations like gsub scale helps you write efficient code and explain your choices clearly in interviews.

Self-Check

"What if the regex pattern was more complex, like including wildcards or repetitions? How would that affect the time complexity?"

Practice

1. What does the Ruby method gsub do when used with a regular expression?

easy

A. It returns the length of the string.

B. It replaces all parts of the string that match the regex with a specified replacement.

C. It deletes the string entirely.

D. It splits the string into an array based on the regex.

Solution

1. Step 1: Understand gsub purpose

   The gsub method is used to replace parts of a string that match a pattern.

2. Step 2: Recognize regex usage

   When used with a regex, it finds all matches and replaces them with the given replacement string.

3. Final Answer:

   It replaces all parts of the string that match the regex with a specified replacement. -> Option B

4. Quick Check:

   gsub with regex = replace all matches [OK]

Hint: Remember: gsub replaces all regex matches in the string [OK]

Common Mistakes:

• Thinking gsub deletes the string
• Confusing gsub with split
• Assuming gsub returns string length

2. Which of the following is the correct syntax to replace all digits in a string with "#" using gsub and regex in Ruby?

easy

A. string.gsub("\d", "#")

B. string.gsub(/d/, "#")

C. string.gsub(/\d/, "#")

D. string.gsub("[0-9]", "#")

Solution

1. Step 1: Identify regex syntax in Ruby

   Regex patterns in Ruby are enclosed in slashes, like /pattern/.

2. Step 2: Match digits correctly

   The regex /\d/ matches any digit character. Using it with gsub replaces all digits.

3. Final Answer:

   string.gsub(/\d/, "#") -> Option C

4. Quick Check:

   Regex in slashes + \d for digits = string.gsub(/\d/, "#") [OK]

Hint: Use slashes / / for regex, not quotes " " [OK]

Common Mistakes:

• Using quotes instead of slashes for regex
• Using wrong regex like /d/ instead of /\d/
• Not escaping backslash properly

3. What is the output of this Ruby code?

text = "Call me at 123-456-7890."
result = text.gsub(/\d/, "*")
puts result

medium

A. Call me at ***-***-****.

B. Call me at 123-456-7890.

C. Call me at \d\d\d-\d\d\d-\d\d\d\d.

D. SyntaxError

Solution

1. Step 1: Understand the regex and replacement

   The regex /\d/ matches every digit character. The replacement is "*".

2. Step 2: Apply gsub to replace digits

   Every digit in the string is replaced by "*", so numbers become stars but other characters stay the same.

3. Final Answer:

   Call me at ***-***-****. -> Option A

4. Quick Check:

   Digits replaced by * = Call me at ***-***-****. [OK]

Hint: Digits \d replaced by * everywhere in string [OK]

Common Mistakes:

• Expecting only first digit replaced
• Confusing regex syntax causing error
• Thinking gsub changes non-digit characters

4. Identify the error in this Ruby code snippet:

sentence = "Hello World!"
sentence.gsub(/world/, "Earth")

What is the problem?

medium

A. Regex is case-sensitive, so 'world' does not match 'World'.

B. Missing replacement string in gsub.

C. Syntax error due to missing parentheses.

D. gsub cannot be used with regex.

Solution

1. Step 1: Check regex matching

   The regex /world/ is lowercase and Ruby regex is case-sensitive by default.

2. Step 2: Compare with string content

   The string has "World" with uppercase W, so the regex does not match anything.

3. Final Answer:

   Regex is case-sensitive, so 'world' does not match 'World'. -> Option A

4. Quick Check:

   Case sensitivity causes no match [OK]

Hint: Remember regex is case-sensitive unless flagged [OK]

Common Mistakes:

• Assuming regex matches ignore case by default
• Thinking gsub needs parentheses around arguments
• Believing gsub can't use regex

5. Given the string data = "User: John_Doe, Email: [e-mail]", which gsub call will replace all non-alphanumeric characters (except underscore) with a dash "-"?

hard

A. data.gsub(/[\w]/, "-")

B. data.gsub(/\w/, "-")

C. data.gsub(/[^a-zA-Z0-9]/, "-")

D. data.gsub(/[^a-zA-Z0-9_]/, "-")

Solution

1. Step 1: Understand character classes

   \w matches letters, digits, and underscore. \W matches anything not in \w.

2. Step 2: Analyze options

   data.gsub(/[^a-zA-Z0-9_]/, "-"): /[^a-zA-Z0-9_]/ matches non-alphanumeric except underscore - correct. data.gsub(/\w/, "-"): /\w/ replaces word chars (alnum + _) - wrong. data.gsub(/[^a-zA-Z0-9]/, "-"): /[^a-zA-Z0-9]/ replaces non-alnum including _ - wrong. data.gsub(/[\w]/, "-"): /[\w]/ replaces word chars - wrong.

3. Final Answer:

   data.gsub(/[^a-zA-Z0-9_]/, "-") -> Option D

4. Quick Check:

   Explicit negated class for alphanumeric + underscore = data.gsub(/[^a-zA-Z0-9_]/, "-") [OK]

Hint: Use negated class [^a-zA-Z0-9_] to keep underscore [OK]

Common Mistakes:

• Using /[^a-zA-Z0-9]/ which replaces underscores too
• Replacing word chars instead of non-word chars
• Confusing \w and \W meaning