LeetCode-1138. 字母板上的路径【哈希表，字符串】
题目描述：解题思路一：首先考虑坐标位置，字符是有序的从0开始，当前字符c的行为(c-'a')/5,列为(c-'a')%5。其次是考虑特殊情况'z'。若当前从‘z’开始则只能往上走;若是其他字符到'z'统一先往左走再往下走。那么每次移动时优先保证选择上移和左移即可。解题思路二：优化判断条件。解题思路三：0
题目描述：
我们从一块字母板上的位置 (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 仅含有小写英文字母。
https://leetcode.cn/problems/alphabet-board-path/description/
解题思路一：首先考虑坐标位置，字符是有序的从0开始，当前字符c的行为(c-‘a’)/5,列为(c-‘a’)%5。其次是考虑特殊情况’z’。若当前从‘z’开始则只能往上走;若是其他字符到’z’统一先往左走再往下走。那么每次移动时优先保证选择上移和左移即可。
class Solution {
public:
string alphabetBoardPath(string target) {
string ans;
int x = 0, y = 0;//当前位置
for (char c:target) {
int nx=(c-'a')/5,ny=(c-'a')%5;//目标位置(x是行，y是列)
if(nx if(ny if(nx>x) ans.append(nx-x,'D');//目标行大，在下边添加nx-x个'D' if(ny>y) ans.append(ny-y,'R');//目标列大，在右边添加ny-y个'R' ans.push_back('!');//取当前字符 x=nx,y=ny;//更新当前位置 } return ans; } }; 时间复杂度：O(n*(r+c))//其中 n表示给定字符串的长度，r表示字母板的行数， c表示字母板的列数。每次移动到新的字符生成移动指令时，需要的时间复杂度为r+c，一共需要生成指令 n 次，因此时间复杂度为O(n×(r+c))。 空间复杂度：O(1) 解题思路二：优化判断条件。 class Solution { public: string alphabetBoardPath(string target) { string ans; int x = 0, y = 0;//当前位置 for (char c:target) { int nx=(c-'a')/5,ny=(c-'a')%5;//目标位置(x是行，y是列) string v(abs(nx-x), "UD"[nx > x]);//竖直（例如nx>x，那么条件为true即是1，取的是nx-x个'D'） string h(abs(ny-y), "LR"[ny > y]);//水平 ans+=(c!='z'?v+h:h+v)+"!";//是z则先竖直后水平，非z相反 x=nx,y=ny;//更新当前位置 } return ans; } }; 时间复杂度：O(n*(r+c))//其中 n表示给定字符串的长度，r表示字母板的行数， c表示字母板的列数。每次移动到新的字符生成移动指令时，需要的时间复杂度为r+c，一共需要生成指令 n 次，因此时间复杂度为O(n×(r+c))。 空间复杂度：O(1) 解题思路三：0 推荐文章
发表评论