Its DFA time! Deterministic Finite Automata + regular expression (complexity). See programmatically compiling RegEx to DFA.