A prefix tree (also called trie) is a rooted tree data structure used to efficiently store a set of words, **S**. In a trie every edge has a letter associated with it. Every node in the trie is associated with the string which we get when we read all the edge letters on the path from the root to this node. So the root of the trie is associated with the empty string and every leaf of the trie is associated with some word from **S**.
A trie is constructed so that from each node at most one child edge is associated with each letter. So not only do all the descendants of a node have a common prefix (which is the string associated with this node) but also every word with this string as prefix is the descendant of this node. It is necessary that for every word from **S** there is a node in trie with which is this word associated.
An example of a trie for the set of words {"aab", "ca"}:
It is not hard to see that if we change the order of letters in the given words then we will get a different trie (constructed from these different words) which might possibly have fewer nodes.
For example the trie constructed from words {"aab","ca"} would have 6 nodes (see image above), but if we change "ca" to "ac" then the trie would have only 5 nodes:
Given String[] **words** which represents the set of words. You are allowed to permute the letters in each word in any way you like. Find the optimal permutation of the letters of the words so the trie constructed from them would have the minimal number of nodes. Return this number of nodes. |