# Alphabet Board Path
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/alphabet-board-path)
Canonical: https://scaleengineer.com/dsa/problems/alphabet-board-path
**Data structures:** Hash Table, String
---
## 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.

![](https://assets.glich.co/dsa/alphabet-board-path/image0.png)

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.

# Approaches
## BFS for Shortest Path
This approach models the alphabet board as a graph where each letter's position is a node. For each character in the target string, it performs a Breadth-First Search (BFS) to find the shortest sequence of moves from the current position to the target character's position. BFS is a standard algorithm for finding the shortest path in an unweighted graph, which guarantees the minimum number of moves.
**Time:** O(N * (V + E)), where N is the length of the target string, V is the number of cells on the board (26), and E is the number of possible moves (at most 4 per cell). Since V and E are constant, the complexity simplifies to O(N). However, the constant factor is significantly larger than the direct simulation approach. · **Space:** O(N) for the output string. The space for the BFS queue and visited set is O(V) where V is the number of cells on the board. Since the board size is constant (26 cells), this is O(1) auxiliary space.
**Pros:** Conceptually straightforward, as it applies a standard shortest path algorithm.; Guaranteed to find a path with the minimum number of moves.
**Cons:** This approach is overly complex for this problem, as the shortest path on a grid can be determined arithmetically (Manhattan distance).; It has a higher constant factor in runtime due to the overhead of managing a queue, a visited set, and path strings.; Inefficient string concatenation within the BFS loop can lead to poor performance if not handled carefully (e.g., with a `StringBuilder` for each path).
### Explanation
The algorithm iterates through the `target` string, character by character. For each character, it treats the current pen position and the target character's position as the start and end nodes in a graph. A BFS is initiated from the start node. The state in the BFS queue stores the current coordinates and the path taken to reach them. We explore neighbors (Up, Down, Left, Right) from the current position. A move is only considered if it leads to a valid position on the board (e.g., moving right from 'z' at `(5,0)` is invalid). A `visited` set is used to avoid cycles and redundant computations. When the BFS reaches the target character's position, the path found is the shortest possible. This path string is appended to the overall result, followed by an '!', and the current position is updated. This process is repeated for all characters in the `target`.

```java
class Solution {
    public String alphabetBoardPath(String target) {
        // Using a map for coordinates for clarity, can be calculated on the fly.
        int[][] pos = new int[26][2];
        for (char c = 'a'; c <= 'z'; c++) {
            int val = c - 'a';
            pos[val][0] = val / 5;
            pos[val][1] = val % 5;
        }

        StringBuilder result = new StringBuilder();
        int currR = 0, currC = 0;

        for (char ch : target.toCharArray()) {
            int targetR = pos[ch - 'a'][0];
            int targetC = pos[ch - 'a'][1];

            if (currR == targetR && currC == targetC) {
                result.append('!');
                continue;
            }

            // BFS to find path from (currR, currC) to (targetR, targetC)
            Queue<Object[]> queue = new LinkedList<>();
            queue.offer(new Object[]{currR, currC, ""});
            Set<String> visited = new HashSet<>();
            visited.add(currR + "," + currC);

            while (!queue.isEmpty()) {
                Object[] current = queue.poll();
                int r = (int) current[0];
                int c = (int) current[1];
                String path = (String) current[2];

                if (r == targetR && c == targetC) {
                    result.append(path).append('!');
                    break;
                }

                // Moves: U, D, L, R
                int[] dr = {-1, 1, 0, 0};
                int[] dc = {0, 0, -1, 1};
                char[] moves = {'U', 'D', 'L', 'R'};

                for (int i = 0; i < 4; i++) {
                    int nextR = r + dr[i];
                    int nextC = c + dc[i];

                    if (isValid(nextR, nextC) && !visited.contains(nextR + "," + nextC)) {
                        visited.add(nextR + "," + nextC);
                        queue.offer(new Object[]{nextR, nextC, path + moves[i]});
                    }
                }
            }
            currR = targetR;
            currC = targetC;
        }
        return result.toString();
    }

    private boolean isValid(int r, int c) {
        if (r < 0 || c < 0 || r > 5 || c > 4) return false;
        if (r == 5 && c > 0) return false;
        return true;
    }
}
```
### Algorithm
- Model the alphabet board as a graph where each letter's position `(r, c)` is a node.
- For each character in the `target` string, do the following:
  - Identify the start position (current pen position) and end position (target character's position).
  - Perform a Breadth-First Search (BFS) starting from the start node to find the shortest path to the end node.
  - The state in the BFS queue should store the current coordinates and the sequence of moves taken to reach there, e.g., `(r, c, path)`.
  - Use a `visited` set to keep track of visited coordinates to avoid redundant explorations and cycles.
  - When exploring neighbors, only consider moves (U, D, L, R) that lead to a valid position on the board.
  - Once the BFS reaches the end node, the path found is guaranteed to be one of the shortest. Append this path and an '!' to the final result.
  - Update the current pen position to the end position.
- After iterating through all characters in `target`, return the accumulated result string.

## Direct Simulation with Safe Move Ordering
This approach directly calculates the required moves without a graph traversal algorithm like BFS. It recognizes that the minimum number of moves between two points on a grid is their Manhattan distance. The main challenge is ensuring that all intermediate moves are on valid board positions, especially when moving to or from the character 'z'. This is solved by a specific, "safe" ordering of moves.
**Time:** O(N), where N is the length of the `target` string. For each character, we perform a constant number of operations (coordinate calculation) and a number of appends proportional to the Manhattan distance, which is bounded by a small constant (max row diff + max col diff = 5 + 4 = 9). · **Space:** O(N) to store the result string, where N is the length of the target. The auxiliary space used is O(1).
**Pros:** Highly efficient with a very low constant factor and no overhead from complex data structures.; Simple and elegant implementation once the move ordering logic is understood.; Correctly handles all edge cases involving the character 'z' due to the safe move ordering.
**Cons:** The logic for the safe move ordering is not immediately obvious and requires careful analysis of the board's constraints, particularly the special case of 'z'.
### Explanation
We start at `(0, 0)`. For each character in the `target`, we calculate its coordinates `(targetR, targetC)`. The core idea is to handle the special case of the 'z' character, which is at `(5, 0)`. Any move into row 5 must land at column 0. Any move out of row 5 must start from column 0. This constraint leads to a specific move ordering. Moves that are always safe or lead to safer regions should be prioritized. 'Up' and 'Left' moves are generally safer than 'Down' and 'Right' moves. 'Down' moves are risky if not aimed at column 0, and 'Right' moves are risky if starting from row 5. A safe sequence is to perform all 'Up' and 'Left' moves before any 'Down' and 'Right' moves. This ensures we never attempt an invalid move. For example, when moving to 'z' `(5, 0)` from `(r, c)`, we first move left to `(r, 0)` and then move down to `(5, 0)`. When moving from 'z', we first move up to a regular row and then move right.

```java
class Solution {
    public String alphabetBoardPath(String target) {
        StringBuilder sb = new StringBuilder();
        int currR = 0, currC = 0;

        for (char ch : target.toCharArray()) {
            int val = ch - 'a';
            int targetR = val / 5;
            int targetC = val % 5;

            // Prioritize Up and Left moves to avoid invalid positions near 'z'.
            while (currR > targetR) {
                sb.append('U');
                currR--;
            }
            while (currC > targetC) {
                sb.append('L');
                currC--;
            }

            // Down and Right moves are performed after.
            while (currR < targetR) {
                sb.append('D');
                currR++;
            }
            while (currC < targetC) {
                sb.append('R');
                currC++;
            }

            sb.append('!');
        }
        return sb.toString();
    }
}
```
### Algorithm
- Initialize the current position `(currR, currC)` to `(0, 0)` and an empty `StringBuilder` for the result.
- Iterate through each character `ch` of the `target` string.
- For each `ch`, calculate its target coordinates `(targetR, targetC)` using the formulas `(ch - 'a') / 5` for the row and `(ch - 'a') % 5` for the column.
- Append moves to the `StringBuilder` to travel from `(currR, currC)` to `(targetR, targetC)`. To ensure path validity, especially around 'z', use a safe move order:
  - First, append 'U' for each step up required (`currR > targetR`). Update `currR`.
  - Second, append 'L' for each step left required (`currC > targetC`). Update `currC`.
  - Third, append 'D' for each step down required (`currR < targetR`). Update `currR`.
  - Fourth, append 'R' for each step right required (`currC < targetC`). Update `currC`.
- After all movement commands for the character are appended, append '!' to the `StringBuilder`.
- After the loop finishes, return the final string from the `StringBuilder`.

# Solutions
### Java

```java
class Solution {
public
  String alphabetBoardPath(String target) {
    StringBuilder ans = new StringBuilder();
    int i = 0, j = 0;
    for (int k = 0; k < target.length(); ++k) {
      int v = target.charAt(k) - 'a';
      int x = v / 5, y = v % 5;
      while (j > y) {
        --j;
        ans.append('L');
      }
      while (i > x) {
        --i;
        ans.append('U');
      }
      while (j < y) {
        ++j;
        ans.append('R');
      }
      while (i < x) {
        ++i;
        ans.append('D');
      }
      ans.append("!");
    }
    return ans.toString();
  }
}

```

### CPP

```cpp
class Solution {
public:
  string alphabetBoardPath(string target) {
    string ans;
    int i = 0, j = 0;
    for (char &c : target) {
      int v = c - 'a';
      int x = v / 5, y = v % 5;
      while (j > y) {
        --j;
        ans += 'L';
      }
      while (i > x) {
        --i;
        ans += 'U';
      }
      while (j < y) {
        ++j;
        ans += 'R';
      }
      while (i < x) {
        ++i;
        ans += 'D';
      }
      ans += '!';
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def alphabetBoardPath(self, target: str) -> str: i = j = 0 ans = [] for c in target: v = ord(c) - ord("a") x, y = v // 5, v % 5 while j > y: j -= 1 ans . append("L") while i > x: i -= 1 ans . append("U") while j < y: j += 1 ans . append("R") while i < x: i += 1 ans . append("D") ans . append("!") return "" . join(ans)

```