Letter Grid Cursor

Medium

A TV on-screen keyboard lays out the letters in a 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

The cursor starts on a (row 0, column 0). The remote has U, D, L and R to move the cursor one cell up, down, left or right (only onto a cell with a letter), and ! to type the letter under the cursor. Return the key presses that type word with as few presses as possible. To make the answer unique, when moving to the next letter press all the needed L first, then U, then R, then D, and only then !. This order never takes the cursor off the grid.

Example 1

word="bug" → 'R!LDDDD!UUUR!'

b is one step right: R!. To u (row 4, column 0): L, then DDDD. To g (row 1, column 1): UUU, then R.

Example 2

word="zoo" → 'DDDDD!UUURRRR!!'

z is straight down: DDDDD!. To o (row 2, column 4): up first, UUU, then right, RRRR. The second o is just another !.

Example 3

word="ya" → 'RRRRDDDD!LLLLUUUU!'

Constraints

1 ≤ len(word) ≤ 100
word consists of lowercase English letters

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Hash Table String

Similar problems

Longest Repeat-Free Stretch Medium Number in Roman Numerals Medium Keypad Words Medium Anagram Buckets Medium Split Into Dictionary Words Medium

Input

word="bug"

Expected

'R!LDDDD!UUUR!'

Run checks the first 3 tests in your browser. Submit checks all 104 tests on the server, hidden ones included.