PrefixTree
Member SRM 491 · 2010-03-12 · by Mimino
Problem Statement
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
Constraints
- words will contain between 1 and 16 elements, inclusive.
- Each element of words will contain between 1 and 50 characters.
- Each element of words will consist of lowercase letters ('a'-'z').
{"topcoder","is","just","a","game","but","it","is","the","best","mmorpg","i","have","ever","played"}
Returns: 37
{"i","hope","you","liked","the","problems"}
Returns: 20
{"merry","christmas","to","everyone"}
Returns: 21
{"a","aabb","bb"}
Returns: 6
{"a","aabb","bb","bbcc","c"}
Returns: 9
{"topcoder"}
Returns: 9
With only one word, every permutation gives the same answer.
{"topcoder","topcoder"}
Returns: 9
Words in the input can repeat. The optimal permutation is the one in which the words are equal.
{"aab","ca"}
Returns: 5
Example from the problem statement. The optimum is if we change "ca" to "ac".
{"aab","ca","ba"}
Returns: 5
The optimum is when the words are: "aba", "ac", "ab".
{"ab","cd","ef"}
Returns: 7
Sometimes nothing can be optimized.
{"a","aa","aaa"}
Returns: 4
One word can be also a prefix of another word.
Submissions are judged against all 143 archived test cases, of which 11 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class PrefixTree with a public method int getNumNodes(vector<string> words) · 143 test cases · 2 s / 256 MB per case