• 力扣每日一题79:单词搜索


    题目描述:

    给定一个 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 更大的情况下可以更快解决问题?

    通过次数

    462.9K

    提交次数

    997.8K

    通过率

    46.4%

    思路和题解:

    回溯和剪枝,设置一个函数check(i,j,k)判断从网格的下标[i][j]位置出发,能不能搜索到单词word[k]...word[wordSize-1](即word中下标k开始的后缀字符串)。判断所有的check(i,j,0),只要有一个为真即为真,否则为假。

    对于check函数,如果board[i][j]!=word[k],return false;如果board[i][j]!=word[k]&&k==wordSize-1,return true;否则就判断相邻的四个位置能不能搜到word[k+1]...word[wordSize-1]。

    要注意的是,check函数中包含了多次递归调用,如果是c++的话,参数写成传引用,这样比值传递运行速度快,能过。值传递的话我试过过不了。

    i代码:

    1. class Solution {
    2. public:
    3. //往右,左,下,上四个方向走时行下标的变化和列下标的变化
    4. int directions[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
    5. bool check(vectorchar>> &board,int m,int n,vectorint>> &visited,int i,int j,string word,int wordSize,int k)
    6. {
    7. if(board[i][j]!=word[k])
    8. return false;
    9. else if(k==wordSize-1)
    10. return true;
    11. visited[i][j]=1;
    12. for(int direc=0;direc<4;direc++)
    13. {//依次往四个方向走
    14. int newi=i+directions[direc][0],newj=j+directions[direc][1];
    15. if(newi>=0&&newi=0&&newj0)
    16. {
    17. bool flag=check(board,m,n,visited,newi,newj,word,wordSize,k+1);
    18. if(flag)
    19. {
    20. return true;
    21. }
    22. }
    23. }
    24. visited[i][j]=0;
    25. return false;
    26. }
    27. bool exist(vectorchar>>& board, string word) {
    28. int m=board.size();
    29. int n=board[0].size();
    30. vectorint>> visited(m,vector<int>(n,0));
    31. int wordSize=word.size();
    32. for(int i=0;i
    33. {
    34. for(int j=0;j
    35. {
    36. bool flag=check(board,m,n,visited,i,j,word,wordSize,0);
    37. if(flag)
    38. return true;
    39. }
    40. }
    41. return false;
    42. }
    43. };

  • 相关阅读:
    AI工人操作行为流程规范识别算法
    【嵌入式】常用串口协议与转换芯片详解
    java随手记
    计算机网络 | 体系结构
    快来学习这个高效绘制流程图的方法
    uniapp 微信小程序使用ec-canvas图表
    day53:day6,人脸识别
    【生信分析】基于TCGA肿瘤数据进行基因共表达网络分析
    从浏览器到堆栈
    poetry(python依赖管理和打包工具)快速入门 && 项目实例
  • 原文地址:https://blog.csdn.net/m0_73441691/article/details/134085682