WolfPrefix | Topcoder Archive

Problem Statement

There are N wolves. Each wolf has a name, but the wolves find them too long to call each other by. Therefore, they've decided to shorten their names. The new names must comply with the following constraints:

For each wolf w, w's shortened name is a prefix of w's original name.
For each wolf w, w's shortened name isn't a prefix of any other wolf's original name.

You are given a String[] S with N elements - names of the wolves. Compute and return the number of ways to shorten the wolves' names, modulo 1,000,000,007.

Definition

Class:: WolfPrefix
Method:: count
Parameters:: String[]
Returns:: int
Method signature:: int count(String[] S)
(be sure your method is public)

Constraints

N will be between 2 and 50, inclusive.
The length of each element of S will be between 1 and 50, inclusive.
Each element of S will consist only of lowercase English letters.

Examples

```
{"ab","ac","bc"}
```
```
Returns: 2
```
The first two wolves' names can't be shortened, because "a" is a prefix of both "ab" and "ac". The last name can be shortened to "b" or left as "bc".
```
{"a","b","c","d","e"}
```
```
Returns: 1
```
All names are 1 character long, so you can't shorten these names any more, but the original (unshortened) set of names is valid.
```
{"pluto","plutorelinquish","plutothefirst"}
```
```
Returns: 0
```
All prefixes of the first name are also prefixes of the other 2 names, so these names can't be shortened at all. Even the unshortened set of names is invalid.

{"aaaa","aabb","bbac","bcc","caaa","caac","ccac","cccc","cdc","cdp"}

Returns: 96

{"aaaaaa","bbbbbb","cc","ddddd","eeeeeeee","fffff","ggggggggggg","hhhhhhhhhhhh","i","jjjjj","kkkkkkkkkkkkkkkkkk","lll","mmmmm","nnnn"}

Returns: 264319930

{"gberovadxzpvqfpplchnqggrqcexzbahqkkornltlsc","oxqlxcjhxgvocwhatbivmcckwejqhhek","bkxdikysgqdhpplwoamqt","vpydpioaqgrxeqffwpfdgpkdvopkwty",
"mjlvxzzhuthnvfssigavqohssgfrrqaxtieimweulbaiszgji","dsioglrw","reptewedqflt","vsftakqmbihhrsd","qxfzxsdxwpawcbbdshhd","rixyarsyukipfu"}

Returns: 270983158

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.