Print Shortest Path to Print a String on Screen in Java
We are able to utilize a remote control to go between the alphabets on a screen that has the letters A through Z on it. The top, bottom, left, and right keys are on the remote.
Determine the most efficient way to use the remote to type each character in the provided string. Every character in the input string should be written in the correct order, starting at the top left position.
The Screen, which is taken as a reference to print the path, is given below.
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 1:
Input:
String s = "HI"
Output:
The shortest path for printing a given string is:
Move Down
Move Right
Move Right
Press OK
Move Right
Press OK
Explanation:
For the given string, the first character is 'H' on the screen, and the letter 'H' is present in the second row. So, move towards down, then move towards right, and then right, and click OK. The second character is 'I', which is beside H; thus, move one step right and click OK, which is the shortest path.
Example 2:
Input:
String s = "HIWORLD"
Output:
The shortest path for printing a given string is:
Move Down
Move Right
Move Right
Press OK
Move Right
Press OK
Move Left
Move Down
Move Down
Move Down
Press OK
Move Up
Move Up
Move Right
Move Right
Press OK
Move Left
Move Left
Move Down
Press OK
Move Up
Move Left
Press OK
Move Up
Move Up
Move Right
Move Right
Press OK
Explanation:
For the given string, the first character is 'H' on the screen, and the letter 'H' is present in the second row. So, move towards down, then move towards right, and then right, and click OK. The second character is 'I', which is beside H; thus, move one step right and click OK, which is the shortest path. Repeat the procedure until the entire string path is printed.
Approach: Using Matrices
The approach is to view the screen as a two-dimensional character matrix. Then, we print the shortest path between the current character and the following character in the matrix after considering each character in the input string one at a time. We take into account the coordinates of the current character and the character after it in the matrix to determine the shortest path. We move left, right, top, or bottom based on the difference between the x and y values of the coordinates of the current and next character. i.e.
We proceed up if the row difference is negative.
We proceed down if the row difference is positive.
We move left if the difference between the columns is negative.
We proceed successfully if the column difference is positive.
Implementation:
FileName: ShortestPathForString.java
import java.io.*;
import java.util.*;
public class ShortestPathForString
{
// function to print the shortest path to
//Use a remote keyboard to enter every character in a given string
static void printPath(String s)
{
int i = 0;
// begin with the character "A," which is at position (0, 0).
int currentX = 0, currentY = 0;
while (i < s.length())
{
// locate the next character's coordinates
int nextcordX = (s.charAt(i) - 'A') / 5;
int nextcordY = (s.charAt(i) - 'B' + 1) % 5;
// If the destination is above, move up.
while (currentX > nextcordX)
{
System.out.println("Move Up");
currentX--;
}
// If the destination is to the left, move left.
while (currentY > nextcordY)
{
System.out.println("Move Left");
currentY--;
}
// If the destination is below, move down.
while (currentX < nextcordX)
{
System.out.println("Move Down");
currentX++;
}
// If the destination is to the right, move right.
while (currentY < nextcordY)
{
System.out.println("Move Right");
currentY++;
}
// The destination has now been reached.
System.out.println("Press OK");
i++;
}
}
public static void main (String[] args)
{
String s = "HIWORLD";
System.out.println("The shortest path for printing a given string is:");
printPath(s);
}
}
Output:
The shortest path for printing a given string is:
Move Down
Move Right
Move Right
Press OK
Move Right
Press OK
Move Left
Move Down
Move Down
Move Down
Press OK
Move Up
Move Up
Move Right
Move Right
Press OK
Move Left
Move Left
Move Down
Press OK
Move Up
Move Left
Press OK
Move Up
Move Up
Move Right
Move Right
Press OK
Complexity Analysis:
When n is the size of the supplied string, the time complexity is expressed as O(n*n). The Space Complexity O(1) is constant because no more space is needed.