PROBLEM STATEMENT
The old fashioned king does not know how to SMS and thus he is having problems sending messages to
the queen. In particular, he is having a problem with a feature called T9.
In T9, the set of alphabets are partitioned into 9 sets, where the i-th set of characters
(1-based) denotes the possible characters that may be typed by pressing digit i. For this problem,
we will use strings to denote a set of characters. On a standard modern cell phone, the following
partition is used
{"", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}
For the partition above, pressing 2 may output 'a', 'b' or 'c'; pressing 3 may output 'd', 'e' or
'f'; and so on. Pressing 223 can give you various outputs of the form "(abc)(abc)(def)" where
(XYZ) means that the letter can be either X or Y or Z. For example, a few possible outputs are
"ace", "bad" and "bbe".
However, not all possible outputs are dictionary words (like "bbe" is not a dictionary word), and
thus these outputs do not make sense. The cell phone considers only those outputs which correspond
to dictionary words. Suppose that there are only two possible dictionary words from
"(abc)(abc)(def)" - namely, "ace" and "bad". Then, the keystrokes 223 gives the output "ace", and
the keystrokes 223# gives the output "bad". In general if a certain number (like 223) corresponds
to multiple dictionary words, then the number followed by n hashes ('#') is used to type the n-th
dictionary word (0-based) from the lexographically sorted list of dictionary words corresponding
to the number. Sometimes the number of hashes typed can be quite large. Hence, we have a special
character star ('*') which is equivalent to 5 contiguous hashes. The digit 0 is used to type a
space.
The king needs to type a text using T9. The text is a string that consists of lowercase letters
('a'-'z') and space characters (' '). A word is a maximal contiguous substring of the text that
contains only lowercase letters ('a'-'z'). The only way the king can type a word is by first
pressing a non-empty sequence of digits ('1'-'9') followed by a (possibly emtpy) sequence of
characters '#' and/or '*'.
You will be given a vector part whose i-th element (1-based) is the set of alphabets
which correspond to the digit i. You will also be given a vector dict that represents a
set of all dictionary words, where each element is a single word. Finally, you will be given a
vector keystr. Concatenate the elements of keystr in the same order as they are given to
obtain a string. This string represents the keystrokes pressed by the king. To help the king,
return the text that will result when the given keystrokes are pressed. You may assume that the
given keystrokes are valid, i.e. each maximal contiguous substring that doesn't contain '0'
characters starts from non-empty sequence of digits ('1'-'9') and then is optionally continued
with a sequence of '#' and/or '*' characters. You may also assume that each such substring
corresponds to a word from dict.
DEFINITION
Class:T9
Method:message
Parameters:vector , vector , vector
Returns:string
Method signature:string message(vector part, vector dict, vector keystr)
NOTES
-A substring of a string is called maximal with respect to some property if it can't be extended
to the left or to the right while maintaining the property.
-A string A is lexicographically less than another string B of the same length if there exists a
position i such that each character of A before the i-th position is equal to the character at the
corresponding position in B, and A[i] is less than B[i].
-For the purpose of this problem, a partition of alphabets into 9 sets may contain any number of
empty sets.
CONSTRAINTS
-part will represent a valid partition of the 26 english alphabets into 9 sets, i.e. it will
consist of exactly 9 elements and every letter from 'a' to 'z' will appear exactly once in exactly
one of the elements of part.
-dict will contain between 1 and 50 elements, inclusive.
-Each element of dict will contain between 1 and 50 characters, inclusive.
-Each character in dict will be a lowercase letter 'a'-'z'.
-All elements of dict will be distinct.
-keystr will contain between 1 and 50 elements, inclusive.
-Each element of keystr will contain between 1 and 50 characters, inclusive.
-Each character in keystr will be one of '0'-'9', '#', '*'.
-The length of the resulting text will be between 1 and 1000, inclusive.
-The string obtained by concatenating the elements of keystr will represent a valid sequence of
keystrokes (as explained in the statement).
EXAMPLES
0)
{"", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}
{"bad"}
{"2230223"}
Returns: "bad bad"
1)
{"", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}
{"the", "tie"}
{"0843#000843#000"}
Returns: " tie tie "
There may be leading, trailing and contiguous spaces.
2)
{"", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}
{"bad", "ace", "aad", "aae", "aaf", "acf", "acd", "the", "tie"}
{"223#02", "23*#00843#0"}
Returns: "aae bad tie "
Don't forget to concatenate the elements of keystr. Also, "*" is equivalent to "#####".
3)
{"", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}
{"the", "tie", "bad", "ace", "aad", "aae", "aaf", "acf", "acd"}
{"84300223#02", "23#*"}
Returns: "the aae bad"
'*' may also appear after the '#'. All that matters is, it is equivalent to "#####".
4)
{"", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}
{"bad", "ace", "aad", "aae", "tie", "aaf", "acf", "acd", "the"}
{"223#02", "23######"}
Returns: "aae bad"
The king may use '*'. But it is not necessary that he uses it everytime he is allowed to use it.
5)
{"", "rq", "lde", "yoauz", "cbfgn", "tjkpx", "wvs", "ih", "m"}
{"xktgmfmoqlmivm",
"hmthr",
"tpjgmnmaremiwm",
"tpjcmnmyrlmhvm",
"xkpnmgmzqdmhsm",
"wqopvvmiig",
"melbcbqeeg",
"jkxnmbmardmhwm",
"kpxnmcmyqlmism",
"wrztvsmhhf",
"srztssmiic",
"pxtgmfmyrdmhwm",
"vqoxswmiin",
"wryksvmihb",
"ptjfmbmoremhvm"}
{"00",
"7246779885##00000089682000007246779885##0000724677",
"9885#000089682000093355523350066659594239879###000"}
Returns: " wqopvvmiig hmthr wqopvvmiig vqoxswmiin hmthr melbcbqeeg
pxtgmfmyrdmhwm "
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)2010, TopCoder, Inc. All rights reserved.