广告区

广告区


本站消息

站长简介/公众号

关注本站官方公众号:程序员总部,领取三大福利!
福利一:python和前端辅导
福利二:进程序员交流微信群,专属于程序员的圈子
福利三:领取全套零基础视频教程(python,java,前端,php)

  价值13000svip视频教程,python大神匠心打造,零基础python开发工程师视频教程全套,基础+进阶+项目实战,包含课件和源码

  出租广告位,需要合作请联系站长

+关注
已关注

分类  

暂无分类

标签  

暂无标签

日期归档  

2021-07(1)

2021-08(13)

Leetcode 1138:字母板上的路径(超详细的解法!!!)

发布于2019-08-20 11:53     阅读(1213)     评论(0)     点赞(22)     收藏(4)



我们从一块字母板上的位置 (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!"
  • 1
  • 2

示例 2:

输入:target = "code"
输出:"RR!DDRR!UUL!R!"
  • 1
  • 2

提示:

  • 1 <= target.length <= 100
  • target 仅含有小写英文字母。

解题思路

这个题目只需要我们计算出字母的坐标,然后计算每次的横纵坐标距离即可。但是有一个麻烦的点就是这个z,这里我用了一点trick,我们只要保证'U''L''D''R'的前面触发即可。

import string
class Solution:
    m = {c: [i // 5, i % 5] for i, c in enumerate(string.ascii_lowercase)}
    def alphabetBoardPath(self, target: str) -> str:
        x0, y0 = 0, 0
        res = ""
        for c in target:
            x, y = self.m[c]
            res += 'L'*max(0, y0 - y) + 'U'*max(0, x0 - x) + 'D'*max(0, x - x0) + 'R'*max(0, y - y0) + '!'
            x0, y0 = x, y
        return res
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

reference:

https://leetcode.com/problems/alphabet-board-path/discuss/345235/Python-Easy-Solution

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!







所属网站分类: 技术文章 > 博客

作者:38373

链接:https://www.pythonheidong.com/blog/article/49141/eebf815658094bceb76d/

来源:python黑洞网

任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任

22 0
收藏该文
已收藏

评论内容:(最多支持255个字符)