PROBLEM STATEMENT
Mr. Frehley just got a new phone number, and he wants an easy way to remember
it. Given the fact that every letter in the alphabet maps to a unique number
on a phone, he decides to figure out the words that can be spelled out with his
phone number. The diagram below shows the standard mapping of letters to
numbers on a phone:
_____ _____ _____
| 1 | | 2 | | 3 |
| | | ABC | | DEF |
|_____| |_____| |_____|
_____ _____ _____
| 4 | | 5 | | 6 |
| GHI | | JKL | | MNO |
|_____| |_____| |_____|
_____ _____ _____
| 7 | | 8 | | 9 |
| PQRS| | TUV | | WXYZ|
|_____| |_____| |_____|
_____
| 0 |
| |
|_____|
So, if Mr. Frehley's phone number was 364, he could spell out "DOG" because "D"
maps to 3, "O" maps to 6, and "G" maps to 4.
Instead of considering all possible words, he decides to limit himself by only
considering words that meet the following two rules:
- no more than two consonants can appear consecutively
- no more than two vowels can appear consecutively
"A", "E", "I", "O", and "U" are vowels. All other letters are consonants
except for the letter "Y", which can be either a consonant or a vowel, but not
both simultaneously - the following examples will clarify this:
- "DOG" meets Mr. Frehley's criteria because it's composed of: 1 consonant, 1
vowel, 1 consonant.
- "PQR" does not meet the criteria because it's composed of: 3 consecutive
consonants.
- "YYY" meets the criteria because each "Y" can be either a consonant or a
vowel - so if the first "Y" is considered a consonant and the other two are
considered vowels, the word is composed of: 1 consonant, 2 consecutive vowels.
- "DRYEA" does not meet the criteria because if the "Y" is considered a vowel,
the word is composed of: 2 consecutive consonants, 3 consecutive vowels. If
the "Y" is considered a consonant, the word is composed of: 3 consecutive
consonants, 2 consecutive vowels. Either way, it does not meet the criteria.
- "TRAINS" meets the criteria because it's composed of: 2 consecutive
consonants, 2 consecutive vowels, 2 consecutive consonants.
Mr. Frehley writes down all the possible words that his phone number can spell
in alphabetically ascending sorted order. Each unique word is written only
once (even those that can be valid in multiple ways - for example, "Y" can be a
valid word when "Y" is either a vowel or a consonant, but it is only counted
once). All words will only consist of upper case letters, and all words must
be exactly the same length as the phone number itself. Return the nth entry in
Mr. Frehley's list. n = 0 refers to the first entry. If n references an entry
that does not exist (for example, there are 3 entries, and n >= 3), return the
empty string ("").
Phone numbers that contain either "1" or "0" cannot spell any words since no
letters map to these digits. In this case, Mr. Frehley's list will be empty.
Implement a class Phone, which contains a method nthWord. This method will
return the nth word in Mr. Frehley's list. As inputs, you are given his phone
number as a String, and n as an int.
DEFINITION
Class: Phone
Parameters: String, int
Returns: String
Method signature (be sure your method is public): String nthWord(String number,
int n);
INPUT CONSTRAINTS
TopCoder will verify that all input constraints are met.
- number will contain only digits (0 - 9, inclusive)
- number will contain between 1 and 8 digits inclusive
- n will be an integer greater than or equal to 0
EXAMPLES:
number: "123"
n: 0
Phone numbers that contain "1" or "0" do not correspond to any words.
return value: ""
-----------------------------
number: "456"
n: 3000
There is no 3000th entry in the list.
return value: ""
-----------------------------
number: "228"
n: 13
All possible words: "AAT", "AAV", "ABT", "ABU", "ABV", "ACT", "ACU", "ACV",
"BAT", "BAU", "BAV", "BBU", "BCU", "CAT", "CAU", "CAV", "CBU", "CCU"
return value: "CAT"
-----------------------------
number: "228"
n: 18
There is no entry at n = 19.
return value: ""
-----------------------------
number: "86726337"
n: 66
return value: "TOPCODER"
-----------------------------
number: "7899"
n: 73
return value: "STYX"
-----------------------------
number: "2328537"
n: 191
return value: "BEATLES"
-----------------------------
number: "93773546"
n: 733
return value: "ZEPPELIN"
-----------------------------
number: "2522262"
n: 150
return value: "ALABAMA"