1138. Alphabet Board Path

题目信息

题号:

1138

难度:

Medium

主题:

字符串、网格路径、构造

原题:

LeetCode 1138

重点:

从字母 a 出发,只能移动到棋盘中实际存在的相邻格;每到目标字母后用 ! 选取,返回任意最短路径

题目重述

字母棋盘前五行依次为 abcde、fghij、klmno、pqrst、uvwxy,最后一行只有字母 z。初始位置在 a。

字符 U、D、L、R 分别表示向上、下、左、右移动一格,且移动后必须仍位于棋盘的有效字母格;字符 ! 表示选取当前位置的字母。给定小写字符串 target,请返回能够依次选出其全部字符的任意最短操作串。

1 <= target.length <= 100,target 只包含小写英文字母。

自建示例

从起点移动到独立的 z 格:

输入:target = "az"
输出:"!DDDDD!"
解释:先在 a 处选取,再沿第一列向下五格到达 z 并选取,共使用最少移动次数。

从 z 返回 a:

输入:target = "za"
输出:"DDDDD!UUUUU!"
解释:先沿第一列到达 z,选取后原路向上返回 a;全过程没有进入 z 所在行中不存在的其他列。