TopCoder problem "T9" used in Member SRM 468 (Division I Level One , Division II Level Two)



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 String[] part whose i-th element (1-based) is the set of alphabets which correspond to the digit i. You will also be given a String[] dict that represents a set of all dictionary words, where each element is a single word. Finally, you will be given a String[] 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:String[], String[], String[]
Returns:String
Method signature:String message(String[] part, String[] dict, String[] keystr)
(be sure your method is public)
    
 

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   "

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10762

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14183&pm=10762

Writer:

keshav_57

Testers:

Rustyoldman , ivan_metelsky , mohamedafattah , it4.kp

Problem categories:

Simulation, String Manipulation