TopCoder problem "NameInput" used in Member SRM 461 (Division II Level Three)



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.
 

Definition

    
Class:NameInput
Method:countUpDownKeyPresses
Parameters:String[], String[]
Returns:int
Method signature:int countUpDownKeyPresses(String[] predictionSequence, String[] name)
(be sure your method is public)
    
 

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.
5)
    
{"abcABC123","cbaCBA321"}
{"aB32C2AaB3c","c32bA"}
Returns: 38

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14181&pm=10747

Writer:

dolphinigle

Testers:

Rustyoldman , timmac , ivan_metelsky , mohamedafattah , it4.kp

Problem categories:

Dynamic Programming