Print Shortest Path to Print a String on Screen

Difficulty Level Easy
Frequently asked in Accolite
Matrix Shortest Path StringViews 2578

Problem Statement

In the “Print Shortest Path to Print a String on Screen” problem we have given a screen containing alphabets from A-Z and input string, by using remote we can go from one character to another character, remote contains only left, right, top, and bottom keys. write a function that will find the shortest path to type all the characters of the given string using the remote.

Input Format

First 5 lines containing 5 characters each and the 6th line containing a single character. These six lines are showing a screen.

7th line containing a string “s”.

Output Format

The first and only one line containing a string containing Moves. U for the move up, D for the move down, R for the move right, L for the move left, and Y for press OK.

Constraints

  • 1<=|s|<=10^6
  • s[i] must be a lower case English alphabet

Example

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
cozy
RRYDDRRYLLLLDDDYURRRRY

Explanation: Here we move in this way. Move Right, Move Right, Press OK, Move Down, Move Down, Move Right, Move Right, Press OK, Move Left, Move Left, Move Left, Move Left, Move Down, Move Down, Move Down, Press OK, Move Up, Move Right, Move Right, Move Right, Move Right, Press OK

Algorithm for Print Shortest Path to Print a String on Screen

In this method, the main idea is to store the characters in the screen as a 2D matrix, consider all characters in the matrix one by one and find the shortest path between the current character and the next character in the matrix

1. Keep track of the position of current character coordinates(ie, currX, currY) and also the next character in string coordinates(ie, nextX, nextY)

2. If row difference is negative, then we move up

3. If the row difference is positive, then we move down

4. If column difference is negative, then move left

5. If column difference is positive, then move right

Implementation

C++ Program for Print Shortest Path to Print a String on Screen

#include <bits/stdc++.h> 
using namespace std; 

int main() 
{ 
  char a[7][5];
  for(int i=0;i<5;i++)
  {
      for(int j=0;j<5;j++)
      {
          cin>>a[i][j];
      }
  }
  cin>>a[6][0];
  int i = 0; 
  int curX = 0, curY = 0; 
  string s;
  cin>>s;
  while(i<s.length()) 
  { 
    int nextX = (s[i] - 'a') / 5; 
    int nextY = (s[i] - 'b' + 1) % 5; 
    while (curX > nextX) 
    { 
      cout<<"U"; 
      curX--; 
    } 
    while (curY > nextY) 
    { 
      cout<<"L"; 
      curY--; 
    } 
    while (curX < nextX) 
    { 
      cout<<"D"; 
      curX++; 
    } 
    while (curY < nextY) 
    { 
      cout<<"R"; 
      curY++; 
    } 
    cout<<"Y"; 
    i++; 
  }
  return 0; 
}

Java Program for Print Shortest Path to Print a String on Screen

import java.util.Scanner;
class sum
{
    public static void main(String[] args)
    {
        Scanner sr = new Scanner(System.in);
        char a[][] = new char [7][5];
        for(int i=0;i<5;i++)
        {
            for(int j=0;j<5;j++)
            {
                a[i][j] = sr.next().charAt(0);
            }
        }
        a[6][0] = sr.next().charAt(0);
        String s = sr.next();
        int i=0;
        int curX = 0;
        int curY = 0;
        while(i<s.length()) 
  { 
    int nextX = (s.charAt(i)-'a') / 5; 
    int nextY = (s.charAt(i)-'b'+1) % 5; 
    while(curX>nextX) 
    { 
      System.out.print("U"); 
      curX--; 
    } 
    while (curY > nextY) 
    { 
      System.out.print("L");
      curY--; 
    } 
    while (curX < nextX) 
    { 
      System.out.print("D");
      curX++; 
    } 
    while (curY < nextY) 
    { 
      System.out.print("R");
      curY++; 
    } 
    System.out.print("Y");
    i++; 
  }
    }
}

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 
tutorial

DDDRRRRYLLLLDYURRRRYUYLLDYUURYULLLYDDRY

Complexity Analysis for Print Shortest Path to Print a String on Screen

Time Complexity

O(9*n) where n is the size of the given string “s”. Here the worst case of time complexity is string “za”. First, we are at (0,0). Now we start traveling toward z and it takes 8 moves to reach at “z”. Now we hit “OK”. So there is a total of 9 moves for reaching “z”. And 9 moves from “z” to “a”. So, our time complexity will be linear.

Space Complexity

O(1) because we don’t use any auxiliary space at here.

Translate »