LikelyWord
SRM 336 · 2007-01-25 · by dgoodman
Problem Statement
We are given k, the length of the new word, and dictionary, a
Constraints
- dictionary will contain between 1 and 50 elements, inclusive.
- Each element of dictionary will contain between 1 and 50 characters, inclusive.
- Each character in each element of dictionary will be a lowercase letter ('a'-'z').
- The elements of dictionary will be distinct and in ascending alphabetical order.
- k will be between 1 and 10, inclusive.
- There will be at least one k-letter word that is not in dictionary.
{"time","zoology"}
1
Returns: 0
There are many more 1 letter words before "time" than either between "time" and "zoology" or after "zoology".
{"az","ma","xz"}
1
Returns: 1
12 words ("b", "c", ..., "m") would have index 1, while 11 ("n", ... , "x") would have index 2.
{"az","ma","xz"}
2
Returns: 2
With the same dictionary but a longer new word, it becomes most likely that the new word will go between "ma" and "xz".
{"a","m","y"}
1
Returns: -1
There are 23 equally likely 1-letter words (since 3 are already in the dictionary). 0 would have index 0, 11 would have index 1, 11 would have index 2, and 1 would have index 3. So no index is most likely.
{"a","g","m","s","z"}
5
Returns: 4
Submissions are judged against all 114 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class LikelyWord with a public method int likely(vector<string> dictionary, int k) · 114 test cases · 2 s / 256 MB per case