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;
    }
}

Comments

  1. Very fancy! Since coordinates of all characters are easy to compute, it's also possible to directly calculate offsets between every segment of the path using simple math:

    from typing import Tuple

    class Solution:
    def alphabetBoardPath(self, target: str) -> str:
    def coords_of(char: str) -> Tuple[int, int]:
    pos = ord(char) - ord("a")
    return pos // 5, pos % 5

    pos, path = (0, 0), ""
    for char in target:
    new_pos = coords_of(char)
    if new_pos[0] < pos[0]:
    path += "U" * (pos[0] - new_pos[0])
    if new_pos[1] < pos[1]:
    path += "L" * (pos[1] - new_pos[1])
    if new_pos[0] > pos[0]:
    path += "D" * (new_pos[0] - pos[0])
    if new_pos[1] > pos[1]:
    path += "R" * (new_pos[1] - pos[1])
    path += "!"
    pos = new_pos

    return path

    ReplyDelete

Post a Comment

Popular posts from this blog

Count Binary Substrings

Count Vowels Permutation: Standard DP

Maximum Number of Balloons