I believe the correct way to protect against ReDOS is to use one of the many regular expression implementations that do not have exponential worst cases.

Nowadays there are good DFA or Tree based matching algorithms that are O(mn) where m is the length of the regular expression and n is the length of the input.

No, seems like it would result in a much bigger state machine that includes states and transitions for all those non-exact matches.

https://en.wikipedia.org/wiki/Finite-state_machine#Acceptors...