Connection Status:
Competition Arena > JohnnysPhone

JohnnysPhone

SRM 370 · 2007-10-09 · by mateuszek

SRM 370 · 2007-10-09 · by mateuszek · Dynamic Programming, String Manipulation
Class Name: JohnnysPhone
Return Type: int
Method Name: minimizePushes
Arg Types: (vector<string>, string)
Problem Statement

Problem Statement

Little Johnny loves sending text messages to his friends. Recently, he bought himself a cool new phone (an Eric-Sonnicson F198-EX32 with MP3 player, GPS navigation, built-in washing machine, and many other features). Johnny's favorite feature is a T9 dictionary that simplifies typing. Here's how T9 works. The 26 letters of the alphabet are assigned to the phone's keypad as follows:
  • 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
The phone also has three special buttons: "Next in dictionary", "New word" and "Space". These are described in the following paragraphs.

To type a word, you press the digit buttons corresponding to the letters in the word one by one. Each time you press a digit button, the T9 feature will automatically find the first word in the dictionary that has a prefix matching the digits you've typed so far. It will then display that prefix. For example, if the dictionary is { "bad", "apple" }, and you press the 2 button, the display will read "b" since "bad" is the first word with a prefix of "a", "b" or "c". If there are multiple words in the dictionary that have a matching prefix, you can press the "Next in dictionary" button to display the next prefix. In this example, pressing "Next in dictionary" will cause the display to change to "a" since "apple" is the next word with a matching prefix (note that dictionary entries are not necessarily in alphabetical order). However, if you then type another 2, the display will read "ba" since "bad" is the only word that matches that prefix. If there are no matches in the dictionary for what you've typed so far, nothing will be displayed. Also, if you press "Next in dictionary" more times than there are words with the prefix you typed, nothing will be displayed. If you type something and press "Next in dictionary" one or more times after that, when you type the rest of the word, T9 will search the dictionary from the place it has finished for the last prefix. (See examples for more clarification.)

To start a new word, you can press the "Space" button, which will insert a space and let you start typing a new word. Alternatively, you can use the unusual "New word" button, which lets you start a new word without inserting a space, leaving the previous word in whatever state it was in. For example, using the above dictionary, you can press 2, then "New word", then 2, and then 7 to type "bap", a word that does not exist in the dictionary. You can also sometimes use this method to type words that are in the dictionary using fewer button presses. Each time you start typing a new word, T9 will search the dictionary from the beginning.

You are given a String[] dictionary. Concatenate the elements of dictionary into a single string. This string will be a space separated list of words in the order that they appear in the dictionary. You will be also given a String message, the message that Johhny wants to type. Return the minimum possible number of button presses required to type the message, or -1 if it is impossible to type the message using the given dictionary.

Constraints

  • dictionary will contain between 1 and 50 elements, inclusive.
  • Each element of dictionary will contain between 1 and 50 characters, inclusive.
  • Each element of dictionary will contain only lowercase letters ('a'-'z') and spaces (' ').
  • dictionary, when concatenated, will be a single space separated list of words, without leading or trailing spaces.
  • message will contain between 1 and 50 characters, inclusive.
  • message will contain only lowercase letters ('a'-'z') and spaces (' ').
Examples
0)
{ "age messagd messagd message" }
"message"
Returns: 8

The most obvious way to type "message" is to type the seven digits corresponding to the letters in order: 6, 3, 7, 7, 2, 4, 3. At this point, the display will read "messagd" since that is the first matching prefix in the dictionary. You would then have to press "Next in dictionary" two times to get to "message". That's a total of 9 button presses. A faster way to type "message" is to first type the digits 6, 3, 7, 7. The display will read "mess". Now, press "New word" to start a new word without inserting a space. Type the digits 2, 4, 3. "age" is the only matching prefix in the dictionary for this second word, so the display will read "message". That only requires 8 button presses.

1)
{ "b a c d" }
"abcd  dcba "
Returns: 23
2)
{ "a b c" }
"d"
Returns: -1
3)
{ "abc bca ", "bac", " cba" }
"abc abc"
Returns: 7
4)
{ "abc bca ", "bac", " cba" }
"abac acab a b c cab"
Returns: 35
24)
{ "gajdkwifpcks iclfabc" }
"gajf"
Returns: -1

The digits corresponding to the letters in "gajf" are 4, 2, 5, 3. If we type the first three digits, the display will read "gaj". At this point, there's no way to get "f" as the next letter. If we type 3, the display will change to "gajd". If we then press "Next in dictionary", it will change to "iclf". "gajf" is impossible to type with the given dictionary.

58)
{ "aaa ", "bbb ", "ccc" }
"ccc"
Returns: 5

When we type 2, the display will read "a". Now we can press "Next in dictionary" two times and the display will read "c". Now we should just press 2 two more times to finish our message. Note, that when we're finishing the message, the T9 doesn't search the dictionary from the beginning but stays where it were before (unless we press "New word").

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

Coding Area

Language: C++17 · define a public class JohnnysPhone with a public method int minimizePushes(vector<string> dictionary, string message) · 72 test cases · 2 s / 256 MB per case

Submitting as anonymous