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.

// My Solution
class Solution {
    int[][] dir = { { -1, 0 }, { 0, -1 }, { 1, 0 }, { 0, 1 } };
    char[] dirChar = { 'U', 'L', 'D', 'R' };

    static class Pair {
        int x, y;
        StringBuilder str;

        Pair(int x, int y, String s) {
            this.x = x;
            this.y = y;
            str = new StringBuilder(s);
        }
    }

    public String alphabetBoardPath(String target) {
        StringBuilder ans = new StringBuilder();
        int x = 0, y = 0;
        for (int i = 0; i < target.length(); i++) {
            Pair node = helperBFS(x, y, target.charAt(i));
            x = node.x;
            y = node.y;
            ans.append(node.str);
        }
        return ans.toString();
    }

    public Pair helperBFS(int x, int y, char c) {
        String[] board = { "abcde", "fghij", "klmno", "pqrst", "uvwxy", "z" };
        Queue<Pair> q = new LinkedList<>();
        q.add(new Pair(x, y, ""));
        while (q.size() != 0) {
            int size = q.size();
            while (size-- > 0) {
                Pair node = q.poll();
                if (board[node.x].charAt(node.y) == c) {
                    node.str.append("!");
                    return node;
                }
                // Marking visited
                board[node.x] = board[node.x].substring(0, node.y) + '0' + board[node.x].substring(node.y + 1);
                for (int i = 0; i < 4; i++) {
                    int newX = node.x + dir[i][0], newY = node.y + dir[i][1];
                    if (((newX >= 0 && newX < 5 && newY >= 0 && newY < 5) || (newX == 5 && newY == 0))
                            && board[newX].charAt(newY) != '0') {
                        String path = node.str.toString() + dirChar[i];
                        q.add(new Pair(newX, newY, path));
                    }
                }
            }
        }
        return null;
    }
}
class Solution {
    public String alphabetBoardPath(String target) {
        int x = 0, y = 0;
        StringBuilder sb = new StringBuilder();
        for (char ch : target.toCharArray()) {
            int x1 = (ch - 'a') % 5, y1 = (ch - 'a') / 5;
            sb.append(String.join("", Collections.nCopies(Math.max(0, y - y1), "U"))
                    + String.join("", Collections.nCopies(Math.max(0, x1 - x), "R"))
                    + String.join("", Collections.nCopies(Math.max(0, x - x1), "L"))
                    + String.join("", Collections.nCopies(Math.max(0, y1 - y), "D")) + "!");
            x = x1;
            y = y1;
        }
        return sb.toString();
    }
}