Find the shortest route in a device to construct a given string
Given a device having left, right, top, and bottom buttons and an OK button to enter a text from a virtual keypad having alphabets from A–Y arranged in a 5 × 5 grid, as shown below. Find the shortest route in the device to construct a given string if we start from the top-left position in the keypad.
For example,
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
The shortest route to construct string TECHIE with the device’s help is BBBRRRRMTTTMLLMBMRMTRM.
The idea is to consider all characters of the specified string, and for each character, print out the shortest route to the next character from it. For finding the shortest route, compare the coordinates of the current character with the coordinates of the next character in the matrix. Based on the difference between the x–coordinate and y–coordinate of the current and next character, move left, right, top, or bottom.
Following is the implementation in C++, Java, and Python based on the above idea:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
#include <iostream> using namespace std; // Find the shortest route in a device to construct the given string void printPath(string str) { // start from the top-left corner with coordinates, i.e., (0, 0) cell int x = 0, y = 0; int n = str.length(); for (int i = 0; i < n; i++) { // find coordinates of the next character int X = (str[i] - 'A') / 5; int Y = (str[i] - 'A') % 5; // if the next character is above the current character while (x > X) { cout << "T"; x--; // Go up } // if the next character is below the current character while (x < X) { cout << "B"; x++; // Go down } // if the next character is to the left of the current character while (y > Y) { cout << "L"; y--; // Go left } // if the next character is to the right of the current character while (y < Y) { cout << "R"; y++; // Go right } // next character is found cout << "M"; } } int main() { string str = "TECHIE"; printPath(str); return 0; } |
Output:
BBBRRRRMTTTMLLMBMRMTRM
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
class Main { // Find the shortest route in a device to construct the given string private static void printPath(String str) { // start from the top-left corner with coordinates, i.e., (0, 0) cell int x = 0, y = 0; for (char c: str.toCharArray()) { // find coordinates of the next character int X = (c - 'A') / 5; int Y = (c - 'A') % 5; // if the next character is above the current character while (x > X) { System.out.print("T"); x--; // Go up } // if the next character is below the current character while (x < X) { System.out.print("B"); x++; // Go down } // if the next character is to the left of the current character while (y > Y) { System.out.print("L"); y--; // Go left } // if the next character is to the right of the current character while (y < Y) { System.out.print("R"); y++; // Go right } // next character is found System.out.print("M"); } } public static void main(String[] args) { String str = "TECHIE"; printPath(str); } } |
Output:
BBBRRRRMTTTMLLMBMRMTRM
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
# Find the shortest route in a device to construct the given string def printPath(s): # start from the top-left corner with coordinates, i.e., (0, 0) cell x = y = 0 for c in s: # find coordinates of the next character X = (ord(c) - ord('A')) // 5 Y = (ord(c) - ord('A')) % 5 # if the next character is above the current character while x > X: print('T', end='') x = x - 1 # Go up # if the next character is below the current character while x < X: print('B', end='') x = x + 1 # Go down # if the next character is to the left of the current character while y > Y: print('L', end='') y = y - 1 # Go left # if the next character is to the right of the current character while y < Y: print('R', end='') y = y + 1 # Go right # next character is found print('M', end='') if __name__ == '__main__': s = 'TECHIE' printPath(s) |
Output:
BBBRRRRMTTTMLLMBMRMTRM
The time complexity of the above solution is O(n.c), where n is the input string’s length and c is a constant less than equal to 10. The auxiliary space required by the program is O(1).
Author: Aditya Goel
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)