网站建设中 模板,网站结构优化怎么做,数字营销理论,WordPress音乐歌单播放器题目链接 Leetcode.1138 字母板上的路径 Rating #xff1a; 1411 题目描述
我们从一块字母板上的位置 (0, 0)出发#xff0c;该坐标对应的字符为 board[0][0]。
在本题里#xff0c;字母板为board [abcde, fghij, klmno, pqr…题目链接 Leetcode.1138 字母板上的路径 Rating 1411 题目描述
我们从一块字母板上的位置 (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!” 提示
1target.length1001 target.length 1001target.length100target仅含有小写英文字母。
分析
字母 c的位置(x,y)是 ((c - a)/5 , (c - a)%5)例如 f的坐标为 ((f - a)/5 , (f - a)%5)为 (1,0)。
我们根据题意直接模拟即可但需要注意一个点 z。 z到j应该是先上再右。 c到z应该是 先左 再下。
时间复杂度O(n)O(n)O(n)
代码
class Solution {
public:string alphabetBoardPath(string target) {string s ;int i 0,j 0;for(auto c:target){int d c - a;int x d / 5, y d%5;//左走while(j y){j--;s L;}//上while(i x){i--;s U;}//右while(j y){j;s R;}//下while(i x){i;s D;}s !;}return s;}
};
