Alphabet Board Path - 407th LeetCode Solved Problem

This is my 407th solved leetcode problem. Here it is: https://leetcode.com/problems/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.

The way to solve it is by doing a BFS. In fact, multiple BFS. The idea is that for each letter in the target, you'll perform a BFS from the current position to the letter. Since the letter is unique in the board, it simplifies things a bit (what if the letters were not unique?). As you traverse the board via DFS, keep track of the moves. You do need to use a hash tablet to avoid repeating some board cells. Hence for each letter perform the DFS, which gives the final complexity as Len(target) * Len(Board), which is relatively fast. Code is below, cheers, ACC.

public class Solution
{
    public string AlphabetBoardPath(string target)
    {
        string[] board = { "abcde",
                            "fghij",
                            "klmno",
                            "pqrst",
                            "uvwxy",
                            "z****"
                            };

        string result = "";
        QueueItem qi = new QueueItem(0, 0, "");
        foreach (char letter in target)
        {
            qi = PathFromPositionToLetter(board, qi.row, qi.col, letter);
            result += qi.move;
        }

        return result;
    }

    private QueueItem PathFromPositionToLetter(string[] board,
                                                int row,
                                                int col,
                                                char letter)
    {
        Queue queue = new Queue();
        Hashtable visited = new Hashtable();
        int key = row * 37 + col;
        visited.Add(key, true);
        QueueItem qi = new QueueItem(row, col, "");
        queue.Enqueue(qi);

        while (queue.Count > 0)
        {
            qi = queue.Dequeue();

            if (board[qi.row][qi.col] == letter)
            {
                qi.move += "!";
                return qi;
            }

            if (qi.row - 1 >= 0 && board[qi.row - 1][qi.col] != '*')
            {
                key = (qi.row - 1) * 37 + qi.col;
                if (!visited.ContainsKey(key))
                {
                    QueueItem nqi = new QueueItem(qi.row - 1, qi.col, qi.move + "U");
                    queue.Enqueue(nqi);
                    visited.Add(key, true);
                }
            }
            if (qi.row + 1 < board.Length && board[qi.row + 1][qi.col] != '*')
            {
                key = (qi.row + 1) * 37 + qi.col;
                if (!visited.ContainsKey(key))
                {
                    QueueItem nqi = new QueueItem(qi.row + 1, qi.col, qi.move + "D");
                    queue.Enqueue(nqi);
                    visited.Add(key, true);
                }
            }
            if (qi.col - 1 >= 0 && board[qi.row][qi.col - 1] != '*')
            {
                key = qi.row * 37 + (qi.col - 1);
                if (!visited.ContainsKey(key))
                {
                    QueueItem nqi = new QueueItem(qi.row, qi.col - 1, qi.move + "L");
                    queue.Enqueue(nqi);
                    visited.Add(key, true);
                }
            }
            if (qi.col + 1 < board[0].Length && board[qi.row][qi.col + 1] != '*')
            {
                key = qi.row * 37 + (qi.col + 1);
                if (!visited.ContainsKey(key))
                {
                    QueueItem nqi = new QueueItem(qi.row, qi.col + 1, qi.move + "R");
                    queue.Enqueue(nqi);
                    visited.Add(key, true);
                }
            }
        }

        return null;
    }
}

public class QueueItem
{
    public int row;
    public int col;
    public string move;

    public QueueItem(int row, int col, string move)
    {
        this.row = row;
        this.col = col;
        this.move = move;
    }
}