I constructed a string for each node and I put the strings in an AVL tree. It executed faster than the solution with the hash function and the unordered map and used far less memory.
The string representing the node looks as follows: it starts with a 0
or 1
, according to whether the node is final or not, and then the pairs (a,n)
are coded as follows: a
is an int
corresponding to the position of the symbol a
in the alphabet and n
is another int
, the index of the node it has transition to with the symbol a
.