Regular expressions with Regex class in Kotlin - Time & Space Complexity

Time Complexity: Regular expressions with Regex class

O(n)

Understanding Time Complexity

We want to understand how the time it takes to check text with a regular expression changes as the text gets longer.

How does the work grow when we use Kotlin's Regex class on bigger input?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

val pattern = Regex("a*b")
val input = "aaaaab"
val result = pattern.matches(input)
println(result)
    

This code checks if the input string matches the pattern "a*b", meaning zero or more 'a's followed by a 'b'.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The Regex engine scans the input string character by character to check the pattern.
• How many times: It goes through the input string once, checking each character in order.

How Execution Grows With Input

As the input string gets longer, the Regex engine spends more time checking each character.

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

Pattern observation: The work grows roughly in direct proportion to the input length.

Final Time Complexity

Time Complexity: O(n)

This means the time to check the pattern grows linearly with the size of the input string.

Common Mistake

[X] Wrong: "Regex matching always takes the same time no matter how long the input is."

[OK] Correct: The Regex engine must look at each character to confirm the pattern, so longer input means more work.

Interview Connect

Understanding how Regex time grows helps you write efficient pattern checks and explain your code clearly in real projects or interviews.

Self-Check

"What if the pattern included nested repetitions like (a+)+b? How would the time complexity change?"

Practice

1. What does the Regex.matches() function do in Kotlin?

easy

A. Finds the first occurrence of the pattern in the string

B. Splits the string by the regex pattern

C. Replaces all matches of the pattern with a new string

D. Checks if the entire input string matches the regex pattern

Solution

1. Step 1: Understand Regex.matches() purpose

   The matches() function returns true only if the whole input string fits the pattern exactly.

2. Step 2: Differentiate from other Regex methods

   Other methods like find() look for parts of the string, but matches() requires full match.

3. Final Answer:

   Checks if the entire input string matches the regex pattern -> Option D

4. Quick Check:

   matches() = full string match [OK]

Hint: matches() means full string must fit pattern exactly [OK]

Common Mistakes:

• Thinking matches() finds partial matches
• Confusing matches() with find()
• Assuming matches() replaces text

2. Which of the following is the correct way to create a Regex object to match digits in Kotlin?

easy

A. val regex = Regex("\\d+")

B. val regex = Regex("\d+")

C. val regex = Regex("\d")

D. val regex = Regex("[d]+")

Solution

1. Step 1: Understand escaping in Kotlin strings

   In Kotlin, backslash must be escaped, so to represent \d (digit), we write "\\d".

2. Step 2: Check the quantifier usage

   "\\d+" means one or more digits, which is correct for matching digits.

3. Final Answer:

   val regex = Regex("\\d+") -> Option A

4. Quick Check:

   Double backslash needed for \d in Kotlin strings [OK]

Hint: Escape backslash twice in Kotlin regex strings [OK]

Common Mistakes:

• Using single backslash without escaping
• Confusing character class syntax
• Missing quantifier '+' for multiple digits

3. What will be the output of this Kotlin code?

val regex = Regex("a.b")
val input = "acb aab aeb"
val matches = regex.findAll(input).map { it.value }.toList()
println(matches)

medium

A. ["acb", "aab", "aeb"]

B. ["acb", "aab"]

C. ["aab", "aeb"]

D. []

Solution

1. Step 1: Understand the regex pattern "a.b"

   The dot '.' matches any single character, so "a.b" matches 'a' + any char + 'b'.

2. Step 2: Check input string matches

   Input has "acb", "aab", and "aeb" all matching the pattern.

3. Final Answer:

   ["acb", "aab", "aeb"] -> Option A

4. Quick Check:

   Dot matches any char between 'a' and 'b' [OK]

Hint: Dot '.' matches any single character in regex [OK]

Common Mistakes:

• Thinking dot matches zero or multiple chars
• Missing some matches in the list
• Confusing findAll with matches

4. Identify the error in this Kotlin code snippet:

val regex = Regex("[a-z")
val result = regex.matches("abc")

medium

A. Missing escape for square brackets

B. Unclosed character class in regex pattern

C. matches() cannot be used with character classes

D. matches() requires a raw string literal

Solution

1. Step 1: Check regex pattern syntax

   The pattern "[a-z" has an opening square bracket but no closing bracket, causing a syntax error.

2. Step 2: Understand consequences

   Regex constructor will throw an exception due to invalid pattern.

3. Final Answer:

   Unclosed character class in regex pattern -> Option B

4. Quick Check:

   Character classes must be closed with ']' [OK]

Hint: Always close character classes with ']' in regex [OK]

Common Mistakes:

• Forgetting to close square brackets
• Thinking matches() needs raw strings
• Confusing escape rules for brackets

5. You want to replace all sequences of one or more spaces in a string with a single dash ('-'). Which Kotlin Regex and method combination correctly does this?

hard

A. Regex("\\s+").replaceAll(input, "-")

B. Regex("\\s*").replace(input, "-")

C. Regex("\\s+").replace(input, "-")

D. Regex("[ ]+").replaceAll(input, "-")

Solution

1. Step 1: Choose correct regex pattern for spaces

   "\\s+" matches one or more whitespace characters; correct for sequences of spaces.

2. Step 2: Use correct Kotlin Regex method

   Kotlin's Regex class uses replace() to replace all matches; replaceAll() does not exist.

3. Final Answer:

   Regex("\\s+").replace(input, "-") -> Option C

4. Quick Check:

   Use replace() with "\\s+" to replace spaces [OK]

Hint: Use replace() with "\\s+" to replace space sequences [OK]

Common Mistakes:

• Using replaceAll() which is not in Kotlin Regex
• Using "\\s*" which matches zero spaces
• Not escaping backslash properly