首页 > 其他分享 >【LeetCode】79. 单词搜索

【LeetCode】79. 单词搜索

时间:2023-12-26 11:33:06浏览次数:36  
标签:return 符合要求 dfs 单词 board len word LeetCode 79

链接:
https://leetcode.cn/problems/word-search/

思路:
利用深度优先遍历

深度优先遍历一般流程:
判断当前是否符合要求
若符合要求,则看更深一层是否符合要求
最后逐层向上返回

代码

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        m, n, l = len(board), len(board[0]), len(word)
        def dfs(i, j, k):
            if k == l: return True
            if i < 0 or j < 0 or i >= m or j >= n or board[i][j] != word[k]:
                return False
            # 标记当前为已访问过
            board[i][j] = ''
            res = dfs(i + 1, j , k + 1) or dfs(i - 1, j, k + 1) or dfs(i, j + 1, k + 1) or dfs(i, j - 1, k + 1)
            # 恢复当前标记
            board[i][j] = word[k]
            return res
        for i in range(m):
            for j in range(n):
                if dfs(i, j, 0):
                    return True
        return False

标签:return,符合要求,dfs,单词,board,len,word,LeetCode,79
From: https://www.cnblogs.com/basilicata/p/17927786.html

相关文章

  • Leetcode LCP 02. 分式化简
    https://leetcode.cn/problems/deep-dark-fraction/description/有一个同学在学习分式。他需要将一个连分数化成最简分数,你能帮助他吗?连分数是形如上图的分式。在本题中,所有系数都是大于等于0的整数。输入的cont代表连分数的系数(cont[0]代表上图的a0,以此类推)。返回一个长度......
  • Leetcode LCP 14. 切分数组
    https://leetcode.cn/problems/qie-fen-shu-zu/description/给定一个整数数组nums,小李想将nums切割成若干个非空子数组,使得每个子数组最左边的数和最右边的数的最大公约数大于1。为了减少他的工作量,请求出最少可以切成多少个子数组。示例1:输入:nums=[2,3,3,2,3,3]......
  • 79.如何获取当前连接id的线程id?
    以下演示是在mysql8.0.25版本中1.PS_CURRENT_THREAD_ID()root@mysqldb21:46:[(none)]>\s;--------------mysqlVer8.0.25forLinuxonx86_64(MySQLCommunityServer-GPL)Connectionid:10#这里可以看到当前的连接id是10Currentdatabase:Cu......
  • 『LeetCode』9. 回文数 Palindrome Number
    题目描述给你一个整数x,如果x是一个回文整数,返回true;否则,返回false。回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。例如,121是回文,而123不是。示例1:输入:x=121输出:true示例2:输入:x=-121输出:false解释:从左向右读,为-121。从右向左读,为121-。因此......
  • 一个利用摸鱼时间背单词的软件
    大家好,我是Java陈序员。最近进入了考试季,各种考试,英语四六级、考研、期末考等。不知道大家的英语四六级成绩怎么样呢?记得大学时,英语四级都是靠高中学习积累的老本才勉强过关。而六级则是考了多次,最终还是折戟沙场,最好的一次是424!不得不说,英语是很重要的,尤其是单词。不管是学......
  • LeetCode-17 电话号码的字母组合
    LeetCode-17电话号码的字母组合给定一个仅包含数字2-9的字符串,返回所有它能表示的字母组合。答案可以按任意顺序返回。给出数字到字母的映射如下(与电话按键相同)。注意1不对应任何字母。示例1:输入:digits="23"输出:["ad","ae","af","bd","be","bf","cd","ce&qu......
  • LeetCode-15 三数之和
    LeetCode-15三数之和给你一个整数数组nums,判断是否存在三元组[nums[i],nums[j],nums[k]]满足i!=j、i!=k且j!=k,同时还满足nums[i]+nums[j]+nums[k]==0。请你返回所有和为0且不重复的三元组。**注意:**答案中不可以包含重复的三元组。示例1:输入:nums=[-1......
  • 『LeetCode』8. 字符串转换整数 (atoi) String to Integer (atoi)
    题目描述请你来实现一个myAtoi(strings)函数,使其能将字符串转换成一个32位有符号整数(类似C/C++中的atoi函数)。函数myAtoi(strings)的算法如下:读入字符串并丢弃无用的前导空格检查下一个字符(假设还未到字符末尾)为正还是负号,读取该字符(如果有)。确定最终结果是负数还是正......
  • [EFI]Gigabyte-Z790-Aorus-Elite-AX-13700K电脑 Hackintosh 黑苹果efi引导文件
    硬件型号驱动情况主板GigabyteZ790AorusEliteaxDDR5处理器I713700K已驱动内存8GBDDR3(orsomethinglikethat)已驱动硬盘WDCPCSN730SDBQNTY-256G-1001已驱动显卡GigabyteRX6600EAGLE8G已驱动声卡RealtekALC285已驱动网卡LucyRTL8125Ethernet已驱动无线网卡+蓝牙Int......
  • [LeetCode Hot 100] LeetCode394. 字符串解码
    题目描述思路思路:碰到数字:压入数字栈,注意多位数的情况碰到字母:直接拼接到res遇到[:将num和res分别压入栈遇到]:开始处理栈顶元素方法一:classSolution{publicStringdecodeString(Strings){intnum=0;StringBuilderres=newStringBuil......