PrefixFreeSubsets
SRM 330 · 2006-12-13 · by soul-net
Problem Statement
A prefix-free set is a set of words in which no element is a prefix of another element in the set. For example {"hello"} , {"hello", "goodbye", "giant", "hi"} and the empty set are examples of prefix-free sets. On the other hand, {"hello","hell"} and {"great","gig","g"} are not prefix-free.
You will be given a
Notes
- A prefix of a string is the result of erasing zero or more characters from the right end of that string.
Constraints
- words will contain between 1 and 50 elements, inclusive.
- Each element of words will contain between 1 and 50 characters, inclusive.
- Each character of each element of words will be a lowercase letter ('a'-'z').
- No two elements of words will be equal.
{"hello","hell","hi"}
Returns: 6
There are 23=8 possible subsets. Only the subsets containing both "hello" and "hell" will not be prefix-free. There are 2 of those (one with "hi" and one without), and therefore, there are 8-2=6 prefix-free subsets.
{"a","b","c","d"}
Returns: 16
All subsets are prefix-free.
{"a","ab","abc","abcd","abcde","abcdef"}
Returns: 7
Only subsets with one or less elements are prefix-free.
{"a","b","aa","ab","ba","bb"}
Returns: 25
{"aaa","aab","aba","abb","baa","bab","bba","bbb","a","b","aa","ab","ba","bb"}
Returns: 676
Submissions are judged against all 112 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class PrefixFreeSubsets with a public method long long cantPrefFreeSubsets(vector<string> words) · 112 test cases · 2 s / 256 MB per case