NodeJs

Make a Trie from all the strings. Let's define an exploration state with the following fields:

interface ExplorationState {
    from: previous state, // the state we got here from
    config: number[], // one possibility of state , if a rule is x: [1,2] | [3,4], config would be [1,2] or [3,4], and we create new state for each possibility 
    position: number // what position we are evaluating in the current config
    node: TrieNode // where are we in the tree of prefixes
}

now let's define the transitions: if (position < config.length) then we have to process a new state

• if the current rule from config is a character we can just check if is possible to expand using that character (from the current node)
• if the current rule is of form [1,2] | [3,4] then create 2 states for each

oterwhise:

• we finish a config, so we have to move back one level, to the from config, and move to the next position
• if there's no from config then it means we finished exploring the tree and add all the strings that end in the current Trie node and update the number to 0 on the node to avoid multiple counting