Alphabet Board Path

Problem

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.

$$ \begin{bmatrix} a & b & c & d & e \\ f & g & h & i & j \\ k & l & m & n & o \\ p & q & r & s & 6 \\ u & v & w & x & y \\ z \end{bmatrix} $$

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.

Examples

Example 1:

1
2


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

Example 2:

1
2


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

Constraints:

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

Solution

Method 1 – Greedy Path Construction

Intuition

The key idea is to always move from the current character’s position to the next target character’s position using the shortest valid path, taking care with the special case of ‘z’, which is alone in the last row. By always moving up/left before down/right when necessary, we avoid invalid board positions.

Approach

Map Characters to Board Positions:

Build a mapping from each letter to its (row, col) position on the board.

Iterate Over Target String:

Start at (0, 0).
For each character in target:
- Find its (row, col) position.
- Move vertically (up or down) to the target row.
- Move horizontally (left or right) to the target column.
- Append ‘!’ to select the character.
- Update the current position.

Handle ‘z’ Carefully:

Always move up before right when moving to ‘z’, and left before down when moving away from ‘z’, to avoid invalid positions.

Build and Return the Resulting Path.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


class Solution {
public:
   string alphabetBoardPath(string target) {
      vector<pair<int, int>> pos(26);
      for (int i = 0; i < 26; ++i)
        pos[i] = {i / 5, i % 5};
      int r = 0, c = 0;
      string ans;
      for (char ch : target) {
        int nr = pos[ch - 'a'].first, nc = pos[ch - 'a'].second;
        // Move up before right to handle 'z'
        while (r > nr) { ans += 'U'; --r; }
        while (c > nc) { ans += 'L'; --c; }
        while (r < nr) { ans += 'D'; ++r; }
        while (c < nc) { ans += 'R'; ++c; }
        ans += '!';
      }
      return ans;
   }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


class Solution {
   public String alphabetBoardPath(String target) {
      int[][] pos = new int[26][2];
      for (int i = 0; i < 26; ++i) {
        pos[i][0] = i / 5;
        pos[i][1] = i % 5;
      }
      int r = 0, c = 0;
      StringBuilder ans = new StringBuilder();
      for (char ch : target.toCharArray()) {
        int nr = pos[ch - 'a'][0], nc = pos[ch - 'a'][1];
        while (r > nr) { ans.append('U'); --r; }
        while (c > nc) { ans.append('L'); --c; }
        while (r < nr) { ans.append('D'); ++r; }
        while (c < nc) { ans.append('R'); ++c; }
        ans.append('!');
      }
      return ans.toString();
   }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


class Solution:
   def alphabetBoardPath(self, target: str) -> str:
      pos: dict[str, tuple[int, int]] = {chr(ord('a') + i): (i // 5, i % 5) for i in range(26)}
      r, c = 0, 0
      ans: list[str] = []
      for ch in target:
        nr, nc = pos[ch]
        # Move up and left first to avoid invalid positions (especially for 'z')
        while r > nr:
           ans.append('U')
           r -= 1
        while c > nc:
           ans.append('L')
           c -= 1
        while r < nr:
           ans.append('D')
           r += 1
        while c < nc:
           ans.append('R')
           c += 1
        ans.append('!')
      return ''.join(ans)

Complexity

⏰ Time complexity: O(N), where N is the length of target.
🧺 Space complexity: O(1) (ignoring output), as the board and mapping are constant size.

Problem#

Examples#

Solution#

Method 1 – Greedy Path Construction#

Intuition#

Approach#

Code#

Complexity#