T9Input

TCO '03 Semifinals 1 · 2003-10-07 · by schveiguy

TCO '03 Semifinals 1 · 2003-10-07 · by schveiguy · Simple Search, Iteration, String Manipulation

Show categories

Class Name: T9Input

Return Type: String[]

Method Name: getKeypresses

Arg Types: (vector<string>)

Problem Statement

With the advent of text messaging on cell phones, a new method for typing has evolved, called T9. The way T9 works is it has a dictionary of words, where each letter is mapped to a number 2-9. The number-letter mappings are fixed, and are printed on the number keys of the phone. For example, 2 corresponds to 'a', 'b', and 'c'. A word is defined as a sequence of lowercase letters. Since most words use different digits for their characters, it is possible to determine which word a user is typing by matching the digit sequence to the letter sequence. Below are all the mappings for the characters used in the problem:

2 - abc
3 - def
4 - ghi
5 - jkl
6 - mno
7 - pqrs
8 - tuv
9 - wxyz
# - <space>
0 - <next word>

So for example, to type "hello world", you would press "43556#96753". A conflict arises when two words have the same digit sequence. So for example, "the" and "tie" both have the same digit sequence - "843". The way T9 handles these conflicts is to display the word that comes first alphabetically. Then, if the word isn't desired, the user must press 0 to get the next word alphabetically, and repeat until the desired word is shown. If the user wishes to enter another word, he/she presses # to insert a space and starts entering the next word. So to input "the tie", you would type "843#8430". It is illegal to press a non-zero digit immediately after pressing '0', the only legal keys you can press after pressing '0' are '0' and '#'.

You will be given a String[] messages, which consists of messages you are to type into your cell phone. messages will only contain spaces and words made entirely of lowercase letters. Assume that the words contained in all of the messages are exactly the words contained in the T9 dictionary. Return a String[] where each element i contains the numeric keypresses you would have to type for element i of messages. Note that messages do not necessarily have to contain words, and can contain sequences of multiple spaces which must be preserved.

Constraints

messages will have between 1 and 50 elements, inclusive.
Each element of messages will have between 0 and 50 characters, inclusive.
Each element of messages will contain only lowercase letters ('a'-'z') and spaces.
There will not be more than 7 words which have the same digit sequence.

Examples

{"the tie", "the tie"}
Returns: { "843#8430",  "843#8430" }

The example from the problem statement.

{" hey joe   ", "   "}
Returns: { "#439#563###",  "###" }

Don't forget to preserve multiple spaces, and to handle messages where there are no words.

{"cba cba cba cba cba cba cba cba", "abc acb bac bca cab cba"}
Returns: { "22200000#22200000#22200000#22200000#22200000#22200000#22200000#22200000",  "222#2220#22200#222000#2220000#22200000" }

Remember that the dictionary contains all words from all the messages, not just the message you are working on.

{"aa ab ac ba bb bc cc cc cc cc cc cc cc cc cc cc cc",
 "cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc",
 "cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc",
 "cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc",
 "cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc",
 "cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc",
 "cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc",
 "cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc",
 "cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc",
 "cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc",
 "cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc",
 "cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc",
 "cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc",
 "cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc",
 "cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc",
 "cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc",
 "cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc",
 "cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc",
 "cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc",
 "cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc",
 "cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc",
 "cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc",
 "cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc",
 "cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc",
 "cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc",
 "cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc",
 "cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc",
 "cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc",
 "cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc",
 "cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc",
 "cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc",
 "cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc",
 "cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc",
 "cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc",
 "cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc",
 "cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc",
 "cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc",
 "cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc",
 "cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc",
 "cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc",
 "cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc",
 "cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc",
 "cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc",
 "cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc",
 "cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc",
 "cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc",
 "cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc",
 "cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc",
 "cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc",
 "cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc cc"}
Returns: { "22#220#2200#22000#220000#2200000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000",  "22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000",  "22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000",  "22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000",  "22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000",  "22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000",  "22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000",  "22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000",  "22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000",  "22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000",  "22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000",  "22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000",  "22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000",  "22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000",  "22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000",  "22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000",  "22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000",  "22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000",  "22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000",  "22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000",  "22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000",  "22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000",  "22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000",  "22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000",  "22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000",  "22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000",  "22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000",  "22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000",  "22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000",  "22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000",  "22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000",  "22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000",  "22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000",  "22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000",  "22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000",  "22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000",  "22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000",  "22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000",  "22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000",  "22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000",  "22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000",  "22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000",  "22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000",  "22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000",  "22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000",  "22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000",  "22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000",  "22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000",  "22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000",  "22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000#22000000" }

{"can you hear me now", "good"}
Returns: { "226#968#4327#63#669",  "4663" }

{"cca ccc c cccb ccca cccc"}
Returns: { "222#2220#2#22220#2222#222200" }

Note that to make "cccc", you cannot use "22202". Pressing '2' after pressing '0' is illegal.

Submissions are judged against all 52 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class T9Input with a public method vector<string> getKeypresses(vector<string> messages) · 52 test cases · 2 s / 256 MB per case