Regular expressions in MATLAB - Time & Space Complexity

Time Complexity: Regular expressions in MATLAB

O(n)

Understanding Time Complexity

When using regular expressions in MATLAB, 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 MATLAB changes when searching bigger strings.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

text = repmat('abc123', 1, n);
pattern = '\d+'; % match one or more digits
matches = regexp(text, pattern, 'match');

This code searches a long string made by repeating 'abc123' n times, looking for digit sequences.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Scanning the input string character by character to find matches.
• How many times: The scan goes through the entire string of length proportional to 6*n.

How Execution Grows With Input

As the input string gets longer, the time to search grows roughly in direct proportion.

Input Size (n)	Approx. Operations
10	About 60 characters scanned
100	About 600 characters scanned
1000	About 6000 characters scanned

Pattern observation: Doubling the input roughly doubles the work done.

Final Time Complexity

Time Complexity: O(n)

This means the time to find matches grows linearly with the length of the input string.

Common Mistake

[X] Wrong: "Regular expressions always run instantly regardless of input size."

[OK] Correct: The search must check each character, so bigger inputs take more time.

Interview Connect

Understanding how regular expression search time grows helps you write efficient code and explain performance clearly.

Self-Check

"What if we changed the pattern to a more complex one with nested groups? How would the time complexity change?"

Practice

1. What does the MATLAB function regexp do?

easy

A. Searches for text patterns in strings

B. Replaces text in strings

C. Sorts arrays numerically

D. Calculates the length of a string

Solution

1. Step 1: Understand the purpose of regexp

   The regexp function in MATLAB is used to find matches of a pattern within text.

2. Step 2: Compare with other functions

   regexprep replaces text, but regexp only searches for patterns.

3. Final Answer:

   Searches for text patterns in strings -> Option A

4. Quick Check:

   regexp = search function [OK]

Hint: Remember: regexp = search, regexprep = replace [OK]

Common Mistakes:

• Confusing regexp with regexprep
• Thinking regexp modifies strings
• Mixing regexp with numeric functions

2. Which of the following is the correct syntax to find all digits in the string 'abc123' using regexp?

easy

A. regexp('abc123', '\\d+')

B. regexp('abc123', '\\w+')

C. regexp('abc123', '\\s+')

D. regexp('abc123', '\\D+')

Solution

1. Step 1: Identify the pattern for digits

   In regular expressions, \d matches digits, and + means one or more.

2. Step 2: Check the options

   regexp('abc123', '\\d+') uses \\d+ which correctly matches one or more digits. Others match word characters, spaces, or non-digits.

3. Final Answer:

   regexp('abc123', '\\d+') -> Option A

4. Quick Check:

   Digits = \d+ pattern [OK]

Hint: Use \\d+ to match one or more digits [OK]

Common Mistakes:

• Using \w+ which matches letters and digits
• Using \s+ which matches spaces
• Using \D+ which matches non-digits

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

str = 'cat bat rat';
matches = regexp(str, '\\b\w{3}\b', 'match');
disp(matches);

medium

A. ['cat', 'bat']

B. ['catbat', 'rat']

C. [] (empty cell array)

D. ['cat', 'bat', 'rat']

Solution

1. Step 1: Understand the pattern '\\b\\w{3}\\b'

   The pattern matches word boundaries \\b around exactly 3 word characters \\w{3}.

2. Step 2: Apply pattern to string

   The string has three 3-letter words: 'cat', 'bat', and 'rat'. All match the pattern.

3. Final Answer:

   ['cat', 'bat', 'rat'] -> Option D

4. Quick Check:

   Three 3-letter words matched [OK]

Hint: \b\w{3}\b matches exactly 3-letter words [OK]

Common Mistakes:

• Ignoring word boundaries and matching partial words
• Expecting concatenated matches
• Confusing \w with digits only

4. The following MATLAB code is intended to replace all digits in str with '#' but does not work as expected:

str = 'Room 101';
newStr = regexprep(str, '\d', '#');
disp(newStr);

What is the error and how to fix it?

medium

A. Pattern should be '\\d+' to replace all digits at once

B. No error; code works correctly

C. Pattern should be '\\D' to match digits

D. Use regexp instead of regexprep

Solution

1. Step 1: Analyze the regexprep usage

   The pattern '\\d' matches any single digit, and regexprep replaces all occurrences by default.

2. Step 2: Check the output

   Replacing each digit with '#' in 'Room 101' results in 'Room ###', which is expected.

3. Final Answer:

   No error; code works correctly -> Option B

4. Quick Check:

   regexprep replaces all matches by default [OK]

Hint: regexprep replaces all matches even with single-digit pattern [OK]

Common Mistakes:

• Thinking \d replaces only one digit total
• Using \D which matches non-digits
• Confusing regexp with regexprep

5. You have a cell array of strings: {'abc123', 'def456', 'ghi789'}. How do you extract only the numeric parts from each string using MATLAB regular expressions?

hard

A. Use regexp(cellArray, '\\d+', 'match')

B. Use regexp(cellArray, '\\w+', 'match')

C. Use regexprep(cellArray, '\\D', '')

D. Use regexprep(cellArray, '\\d+', '')

Solution

1. Step 1: Understand the goal

   We want to keep only digits, removing all non-digit characters.

2. Step 2: Choose the correct function and pattern

   regexprep replaces patterns. Using \\D matches non-digits, so replacing them with empty string keeps only digits.

3. Final Answer:

   Use regexprep(cellArray, '\\D', '') -> Option C

4. Quick Check:

   Remove non-digits with \D pattern [OK]

Hint: Replace non-digits (\D) with empty string to keep digits [OK]

Common Mistakes:

• Using regexp with 'match' returns cell arrays, not strings
• Replacing digits instead of non-digits
• Using \w+ which matches letters and digits