Connection Status:
Competition Arena > QuickT9

QuickT9

SRM 490 · 2010-03-12 · by Chmel_Tolstiy

SRM 490 · 2010-03-12 · by Chmel_Tolstiy · Dynamic Programming, String Manipulation
Class Name: QuickT9
Return Type: int
Method Name: minimumPressings
Arg Types: (vector<string>, string)
Problem Statement

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.

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

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

Coding Area

Language: C++17 · define a public class QuickT9 with a public method int minimumPressings(vector<string> t9, string word) · 92 test cases · 2 s / 256 MB per case

Submitting as anonymous