Find shortest route in a device to construct the given string

Given a device having left, right, top and bottom buttons and a OK button to enter a text from a virtual keypad having alphabets from A-Y arranged in a 5×5 grid as shown below. We need to find the shortest route in device to construct the given string if we start from the top-left position in the keypad.

Keypad:

A B C D E
F G H I J
K L M N O
P Q R S T
U V W X Y

Device:

   T
L  M  R
   B

where,
T – Move up
B – Move down
L – Move left
R – Move right
M – Press OK

 
For example, the shortest route to construct the string TECHIE with the help of device is BBBRRRRMTTTMLLMBMRMTRM.
 

The idea is consider all characters of the specified string and for each character, we print out the shortest route to the next character from it. For finding the shortest route, we compare the coordinates of current character with the coordinates of the next character in the matrix. Based on the difference between x-coordinate and y-coordinate of the current and next character, we move left, right, top or bottom.

C++

Download   Run Code

Output:

BBBRRRRMTTTMLLMBMRMTRM

Java

Download   Run Code

Output:

BBBRRRRMTTTMLLMBMRMTRM

 
Author: Aditya Goel

 
Thanks for reading.

Please use our online compiler to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 



Leave a Reply

avatar
  Subscribe  
Notify of