Given the following grid containing alphabets from A-Z and  a string S.Find the shortest possible path to type all characters of given string in given order using only left,right,up and down movements(while staying inside the grid).Initially you start at A(on the top-left corner).
Find the horizontal movement first(Left/Right) and, then, the vertical movement(Up/Down) for each character of the string.
Grid:
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:
S=GFG
Output:
RIGHT DOWN OK LEFT OK RIGHT OK 
Explanation:
We start at A, go towards G,
then towards F and finally again towards G,
using the shortest paths possible.When You
reach the character, insert "OK" into the
string array.
Example 2:
Input:
S=GEEK
Output:
RIGHT DOWN OK RIGHT RIGHT
RIGHT UP OK OK LEFT LEFT LEFT
LEFT DOWN DOWN OK 
Explanation:
Starting from A, we go 
towards G,then E,we stay at E,Then 
we go towards K using the shortest paths.
Your Task:
You don't need to read input or print anything.Your task is to complete the function ShortestPath() which takes a string S and returns an array of strings containing the order of movements required to cover all characters of S.
Expected Time Complexity: O(N)
Expected Auxillary Space: O(1)
Constraints:
1 ≤ |S| ≤ 10^{6}
S consists of character from A-Z.

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Data structures

Shortest paths

Starter code: #User function Template for python3

class Solution:
    def ShortestPath(self,S):
        #code here

Solutions:
class Solution:

	def ShortestPath(self, S):
		ans = []
		i = 0
		curX = 0
		curY = 0
		while i < len(S):
			nextX = (ord(S[i]) - ord('A')) // 5
			nextY = (ord(S[i]) - ord('B') + 1) % 5
			while curY > nextY:
				ans.append('LEFT')
				curY -= 1
			while curY < nextY:
				ans.append('RIGHT')
				curY += 1
			while curX > nextX:
				ans.append('UP')
				curX -= 1
			while curX < nextX:
				ans.append('DOWN')
				curX += 1
			ans.append('OK')
			i += 1
		return ans


class Solution:

	def ShortestPath(self, S):
		(pr, pc) = (0, 0)
		ans = []
		for i in range(len(S)):
			s = ord(S[i]) - ord('A')
			cr = s // 5
			cc = s % 5
			right = cc - pc
			down = cr - pr
			while right > 0:
				ans.append('RIGHT')
				right = right - 1
			while right < 0:
				ans.append('LEFT')
				right = right + 1
			while down > 0:
				ans.append('DOWN')
				down = down - 1
			while down < 0:
				ans.append('UP')
				down = down + 1
			ans.append('OK')
			pr = cr
			pc = cc
		return ans


class Solution:

	def ShortestPath(self, S):
		ind = 0
		result = []
		(x, y) = (0, 0)
		while ind < len(S):
			new_x = int((ord(S[ind]) - ord('A')) / 5)
			new_y = (ord(S[ind]) - ord('B') + 1) % 5
			while y < new_y:
				result.append('RIGHT')
				y += 1
			while y > new_y:
				result.append('LEFT')
				y -= 1
			while x < new_x:
				result.append('DOWN')
				x += 1
			while x > new_x:
				result.append('UP')
				x -= 1
			result.append('OK')
			ind += 1
		return result


class Solution:

	def ShortestPath(self, S):
		grid = {'A': [0, 0], 'B': [1, 0], 'C': [2, 0], 'D': [3, 0], 'E': [4, 0], 'F': [0, 1], 'G': [1, 1], 'H': [2, 1], 'I': [3, 1], 'J': [4, 1], 'K': [0, 2], 'L': [1, 2], 'M': [2, 2], 'N': [3, 2], 'O': [4, 2], 'P': [0, 3], 'Q': [1, 3], 'R': [2, 3], 'S': [3, 3], 'T': [4, 3], 'U': [0, 4], 'V': [1, 4], 'W': [2, 4], 'X': [3, 4], 'Y': [4, 4], 'Z': [0, 5]}
		position = [0, 0]
		trace = []
		for place in S:
			if grid[place][0] - position[0] > 0:
				for bla in range(grid[place][0] - position[0]):
					trace.append('RIGHT')
			if grid[place][0] - position[0] < 0:
				for bla in range(position[0] - grid[place][0]):
					trace.append('LEFT')
			if grid[place][1] - position[1] > 0:
				for bla in range(grid[place][1] - position[1]):
					trace.append('DOWN')
			if grid[place][1] - position[1] < 0:
				for bla in range(position[1] - grid[place][1]):
					trace.append('UP')
			position = grid[place]
			if grid[place] == position:
				trace.append('OK')
		return trace