JavaScript Print shortest Path to Print a String on Screen
Given a screen with the English alphabet (A-Z) and a remote control with navigation keys (left, right, up, down), we have to determine the most efficient way to write a string using the remote. Starting from the top-left corner of the screen, we need to move through the alphabet to spell out the entire input string in the correct order. In this article, we will see how to find the shortest path to print a string by using Javascript.
Screen:
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
Z
Example:
Input: “HELLO” Output: Right Right OK Up Right Right OK Left Left Left Down Down OK OK Right Right Right OK
The idea is to consider the screen as a 2D matrix of characters. Then we consider all characters of a given string one by one and print out the shortest path between the current character and the next character in the matrix. In order to find the shortest path, we consider the coordinates of the current character and the next character in the matrix. Based on the difference between x and y values of the current and next character’s coordinates, we move left, right, top, or bottom. i.e.
If row difference is negative, we move up
If row difference is positive, we move down
If column difference is negative, we go left
If column difference is positive, we go right
Example: In this Example, we will find shortest path to print a string on screen by using javascript.
Javascript
// Function to print the shortest // possible path to type a given inputString function printShortestPathToTypeString(inputString) { // Initialize current position (0, 0) // and index for the inputString let currentIndex = 0; let currentX = 0, currentY = 0; // Loop through the inputString while (currentIndex < inputString.length) { // Calculate the next position coordinates let nextX = parseInt ((inputString[currentIndex].charCodeAt() - 'A' .charCodeAt()) / 5, 10); let nextY = (inputString[currentIndex].charCodeAt() - 'B' .charCodeAt() + 1) % 5; // Move Up while (currentX > nextX) { console.log( "Up" ); currentX--; } // Move Left while (currentY > nextY) { console.log( "Left" ); currentY--; } // Move Down while (currentX < nextX) { console.log( "Down" ); currentX++; } // Move Right while (currentY < nextY) { console.log( "Right" ); currentY++; } // Press OK to type the character console.log( "OK" ); currentIndex++; } } // Driver code let inputString = "HELLO" ; printShortestPathToTypeString(inputString); |
Down Right Right OK Up Right Right OK Left Left Left Down Down OK OK Right Right Right OK
Time Complexity: O(n*n)
Auxiliary Space: O(1)
Contact Us