Rough Regex and Costs

Intermediate Algorithms and Data Structures English

Also available: Deutsch

Created by Best · 16.08.2026 at 09:13 UTC

Regex are powerful but can backtrack and become expensive. For fixed exact patterns, KMP or indexOf are often clearer and more predictable.

compare naive vs KMP complexity.

Where used

Validation, log extraction, routing rules. Catastrophic backtracking regex is a well-known DoS vector; prefer simple patterns or possessive quantifiers.

Depth

Regular expressions describe sets of strings through concatenation, alternatives, and repetitions. Many practical engines add backreferences and other constructs. As a result, their behavior is more powerful than that of classical finite automata and their runtime is harder to predict.

Ambiguous, nested repetitions can generate many alternative decompositions of the same input. Limited quantifiers, unique subpatterns, or possessive variants reduce such search spaces. For frequently used patterns, it is also worthwhile to compile the pattern once.

Difficulty levels

Read character classes, groups, and quantifiers.
Identify ambiguous repetitions in a pattern.
Formulate a risky pattern semantically equivalent and more clearly.

Pitfalls

A short expression is not automatically cheap. Furthermore, matches in Java means checking the entire input, while find searches for a matching substring.

University approvals: 0

Tasks

Question 1

When is Regex risky?

Always with short literals

In patterns with strong backtracking

Only with HashSet

Only with trees

Question 2

Which change often reduces risky ambiguity while maintaining the same meaning?

Add more nested optional repetitions.

Replace unclear repetitions with clearer or limited sub-patterns.

Copy each group into one another multiple times.

Replace all literals with a dot.

Question 3

Implement matchesDigits. The string must contain at least one decimal digit.

Hint

String.matches(regex) checks the entire string. In a Java string literal, a regex backslash must be written as \.

class DigitRegex {
  static boolean matchesDigits(String s) {
    // TODO
    return false;
  }
}

Starter code is prefilled; replace TODO blocks with your solution.

Runtime output (stdout/stderr)

1 test case will be used for grading

Run checks runtime behavior only. Final correctness is evaluated when you submit.

Card Info

Topic: Algorithms and Data Structures
Difficulty: Intermediate
Completed: 0 users

Creator

Best

BestBuddy