首页 > 其他 > 详细

Leetcode - 79. 单词搜索

时间:2021-09-11 21:46:15      阅读:30      评论:0      收藏:0      [点我收藏+]

给定一个m x n二维字符网格board和一个字符串单词word。如果word存在于网格中,返回true;否则,返回false
单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例 1:
技术分享图片

输入:board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出:true

示例 2:
技术分享图片

输入:board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
输出:true

示例 3:
技术分享图片

输入:board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
输出:false

提示:

  • m == board.length
  • n = board[i].length
  • 1 <= m, n <= 6
  • 1 <= word.length <= 15
  • board 和 word 仅由大小写英文字母组成

进阶:你可以使用搜索剪枝的技术来优化解决方案,使其在board更大的情况下可以更快解决问题?

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/word-search
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

(未完成)解1 2021/9/11 O(?)

from collections import defaultdict

def help_sizhou(a:list, b:list)->bool:
    # 判断b是不是在a的四周
    ax=a[0];ay=a[1]
    bx=b[0];by=b[1]
    if (bx==ax and by==ay+1): return True
    if (bx==ax and by==ay-1): return True
    if (by==ay and bx==ax+1): return True
    if (by==ay and bx==ax+1): return True
    return False

def exist(board: list, word: str) -> bool:
    # 上下左右4个方向,
    # 起点,就是board中所有位置的word[0]
    # 题目限定了m,n∈[1,6],word.len∈[1,15]
    # 由于规模很小,最大也就6x6的格子,word最长也才15个字符,完全可以用dict把word中所有字母在board中的
    # 位置存下来,只不过用过的不能用了要注意
    # dict,存[[x,y],used],坐标,和是否已经使用,
    # 每次用完,记得还原used为0
    d=defaultdict(list)
    m=board.__len__()
    n=board[0].__len__()
    for x in range(0,m):
        for y in range(0,n):
            c=board[x][y]
            if c in word:
                d[c].append([[x,y],0])
    be=word[0]
    if d.get(be)==None: return False
    for x in d[be]:
        rest=word[1:]
        i=x[0][0];j=x[0][1]
        for c in rest:
            # [TODO] 好像这么做并非一个好的选择,还是需要递归,可能还不如顺序的遍历来的简单


if __name__ == ‘__main__‘:
    # true
    board = [["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]]
    word = "ABCCED"
    print(exist(board,word))
    # true
    board = [["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]]
    word = "SEE"
    # false
    board = [["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]]
    word = "ABCB"

Leetcode - 79. 单词搜索

原文:https://www.cnblogs.com/Code2235/p/15253722.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!