Regex Backtracking Pitfalls

Backtracking regex engines are easy to write but can blow up exponentially on patterns with nested quantifiers. Your task is to implement a matcher that avoids catastrophic backtracking by using memoization or an NFA-style approach.

Supported syntax

• Literals: any non-metacharacter
• . matches any single character
• * zero or more of the previous atom
• + one or more of the previous atom
• ? zero or one of the previous atom
• | alternation
• ( ... ) grouping
• \ escapes the next character (treat it literally)

The match must cover the entire input string.

Function signature

func RegexBacktracking(text, pattern string) bool

Examples

RegexBacktracking("aab", "c*a*b") -> true
RegexBacktracking("aa", "a") -> false
RegexBacktracking("ab", ".*") -> true

Constraints

• 0 <= len(text), len(pattern) <= 300

Notes

• A naive recursive backtracking implementation will time out on some tests.
• Use memoization of (node, index) or NFA simulation to keep it linear-ish.