Connection Status:
Competition Arena > NameInput

NameInput

Member SRM 461 · 2009-12-03 · by dolphinigle

Member SRM 461 · 2009-12-03 · by dolphinigle · Dynamic Programming
Class Name: NameInput
Return Type: int
Method Name: countUpDownKeyPresses
Arg Types: (vector<string>, vector<string>)
Problem Statement

Problem Statement

You want to input your name into your personal handheld. Your handheld has only one input method. This input method uses a sequence of characters to predict what character you might input next. The input proceeds according to keys pressed by the user:
  • Initially, the handheld shows the first character in the prediction sequence.
  • If the user presses the 'up' key, the handheld shows the next character in the sequence (or the first character in the sequence if it was showing the last character).
  • If the user presses the 'down' key, it shows the preceeding character in the sequence (or the last character in the sequence if it was showing the first character).
  • If the user presses the 'enter' key, then the character currently shown by the handheld is input (the character shown by the handheld remains the same).
Since you want to input your name, the i-th character input by the handheld must equal the i-th character of your name.

You are given String[] predictionSequence and String[] name. To obtain the prediction sequence of the input method concatenate all elements of predictionSequence. To obtain your name concatenate all elements of name. Return the minimum number of 'up' and 'down' keypresses that are necessary to input your entire name or -1 if it is impossible.

Notes

  • Both your name and the prediction sequence are case sensitive, that is, B is different from b and d is different from D.

Constraints

  • predictionSequence will contain between 1 and 50 elements, inclusive.
  • Each element of predictionSequence will contain between 1 and 50 characters, inclusive.
  • Each character in each element of predictionSequence will be a lowercase letter ('a'-'z'), an uppercase letter ('A'-'Z') or a digit ('0'-'9').
  • name will contain between 1 and 50 elements, inclusive.
  • Each element of name will contain between 1 and 50 characters, inclusive.
  • Each character in each element of name will be a lowercase letter ('a'-'z'), an uppercase letter ('A'-'Z') or a digit ('0'-'9').
Examples
0)
{"Jjhon"}
{"John"}
Returns: 5

Press enter, down, down, enter, down, enter, up, up, enter. This will complete the name input process and use only 5 up and down keypresses.

1)
{"abcdefghijklmnopqrstuvwxyz","ABCDEFGHIJKLMNOPQRSTUVWXYZ","0123456789"}
{"Joh","nAndFr","iends"}
Returns: 186

To obtain the full prediction sequence concatenate all the elements of predictionSequence. To obtain the full name concatenate all the elements of name. This yields "JohnAndFriends".

2)
{"aaaabbbab","baabbabaabba"}
{"bbaaababba","baababababbb"}
Returns: 16

Multiple occurences of characters may be present in both parameters.

3)
{"john"}
{"John"}
Returns: -1

Since it is case sensitive it is impossible to input the letter 'J'.

4)
{"4"}
{"4444444444444"}
Returns: 0

Press enter 13 times.

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

Coding Area

Language: C++17 · define a public class NameInput with a public method int countUpDownKeyPresses(vector<string> predictionSequence, vector<string> name) · 127 test cases · 2 s / 256 MB per case

Submitting as anonymous