Algorithm


Problem Name: 1138. Alphabet Board Path

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.

Code Examples

#1 Code Example with Javascript Programming

Code - Javascript Programming


const alphabetBoardPath = function(target) {
  let sx = 0,
    sy = 0;
  let dir = "";
  let a = "a".charCodeAt(0);
  for (let c of target) {
    let dx = (c.charCodeAt(0) - a) % 5,
      dy = ((c.charCodeAt(0) - a) / 5) >> 0,
      n;
    if (sx > dx) {
      n = sx - dx;
      while (n--) dir += "L";
    }
    if (sy  <  dy) {
      n = dy - sy;
      while (n--) dir += "D";
    }
    if (sy > dy) {
      n = sy - dy;
      while (n--) dir += "U";
    }
    if (sx  <  dx) {
      n = dx - sx;
      while (n--) dir += "R";
    }
    dir += "!";
    (sx = dx), (sy = dy);
  }
  return dir;
};
Copy The Code & Try With Live Editor

Input

x
+
cmd
target = "leet"

Output

x
+
cmd
"DDR!UURRR!!DDD!"

#2 Code Example with Python Programming

Code - Python Programming


class Solution:
    def alphabetBoardPath(self, target: str) -> str:
        ind = {s: [i // 5, i % 5] for i, s in enumerate(string.ascii_lowercase)}
        x = y = 0
        res = ""
        for c in target:
            xx, yy = ind[c]
            if yy < y:
                res += 'L' * (y - yy)
            if xx > x:
                res += 'D' * (xx - x)
            if xx < x:
                res += 'U' * (x - xx)
            if yy > y:
                res += 'R' * (yy - y)
            res += '!'
            x, y = xx, yy
        return res
Copy The Code & Try With Live Editor

Input

x
+
cmd
target = "leet"

Output

x
+
cmd
"DDR!UURRR!!DDD!"
Advertisements

Demonstration


Previous
#1137 Leetcode N-th Tribonacci Number Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#1139 Leetcode Largest 1-Bordered Square Solution in C, C++, Java, JavaScript, Python, C# Leetcode