The number of states is exponential for a general regex. This regex has an NFA closely resembling the trie for the dictionary. There could be at most one live state per depth in the trie. So the number of possible states is bounded at least by (words in dictionary)^(length of longest word). Really much smaller because the states at different levels have to share prefixes.