【力扣-LeetCode】1138. 字母板上的路径-C++题解

1138. 字母板上的路径

难度中等98收藏分享切换为英文接收动态反馈

我们从一块字母板上的位置 (0, 0) 出发，该坐标对应的字符为 board[0][0]。

在本题里，字母板为board = ["abcde", "fghij", "klmno", "pqrst", "uvwxy", "z"]，如下所示。

我们可以按下面的指令规则行动：

• 如果方格存在，'U' 意味着将我们的位置上移一行；

• 如果方格存在，'D' 意味着将我们的位置下移一行；

• 如果方格存在，'L' 意味着将我们的位置左移一列；

• 如果方格存在，'R' 意味着将我们的位置右移一列；

• '!' 会把在我们当前位置 (r, c) 的字符 board[r][c] 添加到答案中。

（注意，字母板上只存在有字母的位置。）

返回指令序列，用最小的行动次数让答案和目标 target 相同。你可以返回任何达成目标的路径。

示例 1：

输入：target = "leet"

输出："DDR!UURRR!!DDD!"

示例 2：

输入：target = "code"

输出："RR!DDRR!UUL!R!"

提示：

• 1 <= target.length <= 100

• target 仅含有小写英文字母。

解题思路：构建字母-坐标映射，模拟搜索路径。

AC代码：

class Solution {
public:struct Point{int r,c;Point(int RR,int CC){r=RR;c=CC;}Point(){}};string alphabetBoardPath(string target) {// 1、获取目标字母的坐标map<char,Point> index;char C='a';int cnt=0;for(int line=0;cnt<26;line++){for(int row=0;row<5 && cnt<26;row++){Point P(line,row);index[C]=P;cnt++;C+=1;}}vector<Point> PTS;for(int i=0;i<target.length();i++){PTS.push_back(index[target[i]]);}string path="";// 2. 模拟搜索路径for(int i=0;i<PTS.size();i++){ // former->curPoint former;if(i==0)former=Point(0,0);elseformer=PTS[i-1];Point cur=PTS[i];if(cur.r==former.r && cur.c==former.c){path+="!";continue;}if(cur.c<former.c)for(int i=1;i<=former.c-cur.c;i++)path+="L";if(cur.r>former.r){}for(int i=1;i<=cur.r-former.r;i++)path+="D";if(cur.r<former.r)for(int i=1;i<=former.r-cur.r;i++)path+="U";if(cur.c>former.c)for(int i=1;i<=cur.c-former.c;i++)path+="R";path+="!";}return path;//simulate// (0,0)->(2,1): 3 steps// (2,1)->(0,4): 2+3=5 steps// (0,4)->(3,4): 3 steps// sum=3+5+3+4=15 steps}
};