TopCoder problem "PrefixFreeSubsets" used in SRM 330 (Division I Level Two)



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 String[] words containing a set of words, and you must return the number of subsets of words that are prefix-free. Note that both the empty set and the entire set count as subsets.

 

Definition

    
Class:PrefixFreeSubsets
Method:cantPrefFreeSubsets
Parameters:String[]
Returns:long
Method signature:long cantPrefFreeSubsets(String[] words)
(be sure your method is public)
    
 

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.
 

Examples

0)
    
{"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.
1)
    
{"a","b","c","d"}
Returns: 16
All subsets are prefix-free.
2)
    
{"a","ab","abc","abcd","abcde","abcdef"}
Returns: 7
Only subsets with one or less elements are prefix-free.
3)
    
{"a","b","aa","ab","ba","bb"}
Returns: 25

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=7255

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10010&pm=7255

Writer:

soul-net

Testers:

PabloGilberto , brett1479 , Olexiy , misof

Problem categories:

Dynamic Programming, Sorting