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 characterboard[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 <= 100targetconsists only of English lowercase letters.
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
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:
Reply Deletefrom 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
Post a Comment
[γγ¬γΌγ ]