LeetCode [1138] Alphabet Board Path

 1138. Alphabet Board Path

Medium

On an alphabet board, we start at position (0, 0), corresponding to character board[0][0].

Here, board = ["abcde", "fghij", "klmno", "pqrst", "uvwxy", "z"], as shown in the diagram below.

We may make the following moves:

• 'U' moves our position up one row, if the position exists on the board;
• 'D' moves our position down one row, if the position exists on the board;
• 'L' moves our position left one column, if the position exists on the board;
• 'R' moves our position right one column, if the position exists on the board;
• '!' adds the character board[r][c] at our current position (r, c) to the answer.

(Here, the only positions that exist on the board are positions with letters on them.)

Return a sequence of moves that makes our answer equal to target in the minimum number of moves.  You may return any path that does so.

 

Example 1:

Input: target = "leet"
Output: "DDR!UURRR!!DDD!"

Example 2:

Input: target = "code"
Output: "RR!DDRR!UUL!R!"

 

Constraints:

• 1 <= target.length <= 100
• target consists only of English lowercase letters.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

class Solution { public String alphabetBoardPath(String target) { int i=0, j=0, pos=0, n = target.length(); String path=""; while(pos<n){ int ch = i*5+j+'a';//char at [i,j] while(pos<n && ch==target.charAt(pos)){ path += "!"; pos++; } if(pos==n){ return path; } int nexChar = target.charAt(pos)-'a'; int nextRow = nexChar/5, nextCol = nexChar%5; char d; if(nextRow<i){ i--; d = 'U'; }else if(nextCol<j){ j--; d = 'L'; }else if(nextRow>i){ i++; d = 'D'; }else{ j++; d = 'R'; } path+=d; } return ""; } }