Regular expressions in R in R Programming - Time & Space Complexity

Time Complexity: Regular expressions in R

O(n)

Understanding Time Complexity

When using regular expressions in R, it is important to understand how the time to find matches grows as the input text gets longer.

We want to know how the work done by R changes when searching through bigger strings.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

text <- c("apple", "banana", "apricot", "cherry", "avocado")
pattern <- "^a"
matches <- grep(pattern, text)
    

This code searches a list of words to find those starting with the letter 'a'.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking each word against the regular expression pattern.
• How many times: Once for each word in the list.

How Execution Grows With Input

As the number of words grows, the time to check all words grows roughly in direct proportion.

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

Pattern observation: Doubling the number of words doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to find matches grows directly with the number of words you check.

Common Mistake

[X] Wrong: "Regular expressions always take the same time no matter how many words there are."

[OK] Correct: Each word must be checked, so more words mean more work and more time.

Interview Connect

Understanding how regular expression matching scales helps you write efficient code and explain your choices clearly in interviews.

Self-Check

"What if we changed the pattern to a more complex one that can backtrack? How would the time complexity change?"

Practice

1. What does the grepl() function do in R when used with regular expressions?

easy

A. It checks if a pattern exists in a string and returns TRUE or FALSE.

B. It replaces all occurrences of a pattern in a string.

C. It extracts all matches of a pattern from a string.

D. It splits a string into parts based on a pattern.

Solution

1. Step 1: Understand the purpose of grepl()

   grepl() returns a logical value indicating if the pattern is found in the string.

2. Step 2: Compare with other functions

   Functions like gsub() replace text, and strsplit() splits strings, so they do not match grepl()'s behavior.

3. Final Answer:

   It checks if a pattern exists in a string and returns TRUE or FALSE. -> Option A

4. Quick Check:

   grepl() = logical check [OK]

Hint: Remember: grepl() returns TRUE/FALSE if pattern found [OK]

Common Mistakes:

• Confusing grepl() with gsub() which replaces text
• Thinking grepl() extracts matched text
• Assuming grepl() splits strings

2. Which of the following is the correct syntax to replace all occurrences of "cat" with "dog" in the string "cat and cat" using regular expressions in R?

easy

A. sub("cat", "dog", "cat and cat")

B. str_replace_all("cat and cat", "cat", "dog")

C. gsub("cat", "dog", "cat and cat")

D. replace("cat", "dog", "cat and cat")

Solution

1. Step 1: Identify function for replacing all occurrences

   gsub() replaces all matches, while sub() replaces only the first.

2. Step 2: Check syntax correctness

   gsub(pattern, replacement, string) is the correct order and usage in R.

3. Final Answer:

   gsub("cat", "dog", "cat and cat") -> Option C

4. Quick Check:

   Replace all = gsub() [OK]

Hint: Use gsub() to replace all matches, sub() only first [OK]

Common Mistakes:

• Using sub() when all occurrences need replacement
• Using non-existent replace() function in base R
• Confusing argument order in functions

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

text <- c("apple", "banana", "apricot", "berry")
matches <- grepl("^a", text)
matches

medium

A. [FALSE, TRUE, FALSE, TRUE]

B. [FALSE, FALSE, FALSE, FALSE]

C. [TRUE, TRUE, TRUE, TRUE]

D. [TRUE, FALSE, TRUE, FALSE]

Solution

1. Step 1: Understand the pattern "^a"

   The caret (^) means the string must start with 'a'. So strings starting with 'a' match.

2. Step 2: Check each string in text

   "apple" and "apricot" start with 'a' (TRUE), "banana" and "berry" do not (FALSE).

3. Final Answer:

   [TRUE, FALSE, TRUE, FALSE] -> Option D

4. Quick Check:

   ^a matches start with 'a' = [TRUE, FALSE, TRUE, FALSE] [OK]

Hint: ^ means start of string; check which words start with 'a' [OK]

Common Mistakes:

• Ignoring ^ and matching 'a' anywhere
• Confusing TRUE/FALSE order in output
• Assuming grepl returns matched strings instead of logical

4. The following R code is intended to replace the first digit in a string with "#" but does not work as expected:

text <- "abc123"
result <- sub("[0-9]", "#", text)
print(result)

What is the problem and how to fix it?

medium

A. Pattern should be "\\d" instead of "[0-9]" for digits in R regex.

B. No problem; code works correctly and replaces first digit.

C. Use gsub() instead of sub() to replace all digits, not just first.

D. The replacement string "#" must be escaped as "\\#".

Solution

1. Step 1: Check the pattern and function

   [0-9] matches any digit; sub() replaces the first match only.

2. Step 2: Verify the output

   Replacing first digit '1' with '#' in "abc123" results in "abc#23", which is expected.

3. Final Answer:

   No problem; code works correctly and replaces first digit. -> Option B

4. Quick Check:

   sub() replaces first digit correctly [OK]

Hint: sub() replaces first match; [0-9] matches digits [OK]

Common Mistakes:

• Thinking [0-9] is invalid in R regex
• Confusing sub() with gsub() for all replacements
• Believing replacement '#' needs escaping

5. You have a vector of email addresses:

emails <- c("[e-mail]", "admin@sitecom", "[e-mail]")

Which regular expression pattern would correctly identify emails ending with ".com" using grepl()?

hard

A. "\\.com$"

B. ".com"

C. "com$"

D. "\\.com"

Solution

1. Step 1: Understand the pattern requirements

   We want to match emails ending exactly with ".com". The dot must be escaped as "\\." to match a literal dot, and "$" means end of string.

2. Step 2: Analyze each option

   "\\.com$" uses "\\.com$" which matches '.com' at the end. ".com" matches any character before 'com', not necessarily end. "com$" misses the dot. "\\.com" matches '.com' anywhere, not necessarily at end.

3. Final Answer:

   "\\.com$" -> Option A

4. Quick Check:

   Escape dot and use $ for end match [OK]

Hint: Escape dot with \\. and use $ to match string end [OK]

Common Mistakes:

• Not escaping dot, so matches any character
• Missing $ causing partial matches
• Confusing string end anchor with start anchor