TopCoder problem "QuickT9" used in SRM 490 (Division I Level Two)



Problem Statement

    Most modern mobile phones include T9 technology for typing text messages faster, and your brand new mobile phone is not an exception.



Your mobile phone has the standard keyboard layout:

  Button     Letters
    2         a,b,c
    3         d,e,f
    4         g,h,i
    5         j,k,l
    6         m,n,o
    7        p,q,r,s
    8         t,u,v
    9        w,x,y,z
T9 requires a dictionary of words. At each moment, T9 maintains three strings: D -- the current combination of digits, F -- the "fixed" part of the message and U -- the "unfixed" part of the message. The message displayed on the phone's screen consists of the "fixed" part immediately followed by the "unfixed" part, i.e., it appears as F + U. The current combination of digits D is only stored in memory and not displayed. There always is the following correspondence between D and U: they have the same length and the i-th character in U is a letter written on the button with digit equal to the i-th character in D. Additionally, the string U must always be such that there's at least one word in the dictionary that starts with U. For a given combination of digits D, we will call a string U valid if it satisfies the described conditions.



When you start typing a new message, all three strings D, F and U are empty. Then you may do the following:
  • press one of the digit buttons (2-9): first, the pressed digit is added to the end of D, then U is changed to the lexicographically earliest string that is valid for the new value of D. If there are no such strings, the button press is ignored, so the values of D and U remain the same as before the button press.
  • press the Right button: first, U is appended to the end of F, then both D and U are reset to empty strings.
  • press the C button: U is appended to the end of F, then both D and U are reset to empty strings, finally, if F is not empty, the last character is removed from F.
  • press the * button: U is changed to the lexicographically next string valid for the current value of D. If there is no such string, it is set to the lexicographically smallest valid string again.
T9 technology is very useful when you need to type a message consisting of dictionary words. However there is a small drawback - typing a word that is not contained in the dictionary becomes much more difficult, so usually you have to type this word part by part (turning T9 off is not considered).



The problem you are facing now is to type a given word using T9. Return the smallest number of button presses needed to type this word on your mobile phone if it is possible at all, otherwise return -1. The word is considered to be typed if F is equal to the word and U is empty.



The dictionary is given in String[] t9. Each element of t9 is a list of words from the dictionary separated by single spaces.
 

Definition

    
Class:QuickT9
Method:minimumPressings
Parameters:String[], String
Returns:int
Method signature:int minimumPressings(String[] t9, String word)
(be sure your method is public)
    
 

Notes

-If two Strings A and B have the same length, then A comes before B lexicographically if it has an alphabetically earlier character at the first position where the Strings differ.
-It's possible that the dictionary contains multiple occurrences of the same word.
 

Constraints

-t9 will contain between 1 and 50 elements, inclusive.
-Each element of t9 will contain between 1 and 50 characters, inclusive.
-Each element of t9 will contain only lowercase letters ('a'-'z') and spaces, and will contain no leading, trailing or consecutive spaces.
-word will contain between 1 and 50 characters, inclusive.
-word will contain only lowercase letters ('a'-'z').
 

Examples

0)
    
{"aae", "bab", "abad", "bdbd", "beta"}
"babe"
Returns: 9
   Button  Result (the "unfixed" part of message in quotes)
1)   2      "a"          (beginning of "aae")
2)   2      "aa"         (beginning of "aae")
3)   2      "aba"        (beginning of "abad")
4)   *      "bab"        (beginning of "bab")
5)   C      ba
6)   2      ba"a"        (beginning of "aae")
7)   3      ba"bd"       (beginning of "bdbd")
8)   *      ba"be"       (beginning of "beta")
9) Right    babe
1)
    
{"ann","ie"}
"annie"
Returns: 7
   Button  Result (the "unfixed" part of message in quotes)
1)   2      "a"          (beginning of "ann")
2)   6      "an"         (beginning of "ann")
3)   6      "ann"        (beginning of "ann")
4) Right    ann
5)   4      ann"i"       (beginning of "ie")
6)   3      ann"ie"      (beginning of "ie")
7) Right    annie
2)
    
{"ann","amm"}
"annie"
Returns: -1
3)
    
{"aaa aab","aac aba abb ccca"}
"aba"
Returns: 6
   Button  Result (the "unfixed" part of message in quotes)
1)   2      "a"          (beginning of "aaa")
2)   2      "aa"         (beginning of "aaa")
3)   *      "ab"         (beginning of "aba")
4) Right    ab
5)   2      ab"a"        (beginning of "aaa")
6) Right    aba
4)
    
{"acac aba aaab","aab aa baa","bba bacade abb","baba"}
"abbaca"
Returns: 10
   Button  Result (the "unfixed" part of message in quotes)
1)   2      "a"          (beginning of "aa")
2)   2      "aa"         (beginning of "aa")
3)   *      "ab"         (beginning of "aba")
4) Right    ab
5)   2      ab"a"        (beginning of "aa")
6)   2      ab"aa"       (beginning of "aa")
7)   2      ab"aaa"      (beginning of "aaab")
8)   2      ab"aaab"     (beginning of "aaab")
9)   3      ab"bacad"    (beginning of "bacade")
10)  C      abbaca
5)
    
{"aaa aab aac","aba abb","ccca"}
"ccc"
Returns: 5

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14243&pm=11228

Writer:

Chmel_Tolstiy

Testers:

PabloGilberto , ivan_metelsky , pieguy

Problem categories:

Dynamic Programming, String Manipulation