# [leetcode] 79. Word Search

[leetcode] 79. Word Search

## Description

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example:

board =[  ['A','B','C','E'],  ['S','F','C','S'],  ['A','D','E','E']]Given word = "ABCCED", return true.Given word = "SEE", return true.Given word = "ABCB", return false.



## 分析

[En]

The meaning of the title is: to judge whether there is a word made up of a path in the character matrix is equal to the word given by the topic.

• 深度优先搜索题目，这是一个经典的递归搜索的题目，终止条件为遍历到word单词的末尾字符了。循环体注意不要超过这个矩阵的边界，因此需要isOut判断一下。

## 代码

class Solution {public:    bool exist(vector>& board, string word) {        int rows=board.size();        int cols=board[0].size();        for(int i=0;i            for(int j=0;j                if(board[i][j]==word[0]){                    if(DFS(board,word,0,i,j)){                        return true;                    }                }            }        }        return false;    }        bool DFS(vector>& board, string word,int start,int row,int col){        if(start>=word.size()){            return true;        }        if(isOut(row,col,board.size(),board[0].size())){            return false;        }        if(board[row][col]!=word[start]){            return false;        }        int dx[]={0,0,1,-1};        int dy[]={1,-1,0,0};        char temp=board[row][col];        board[row][col]='.';        for(int i=0;i            if(DFS(board,word,start+1,row+dx[i],col+dy[i])){                return true;            }        }        board[row][col]=temp;        return false;    }        bool isOut(int row,int col,int rows,int cols){        return row=rows||col>=cols;    }};


## 参考文献

• 收藏
• 评论
• *举报

Original: https://blog.51cto.com/u_9453611/5569523
Author: 是念
Title: [leetcode] 79. Word Search

(0)

### 大家都在看

• #### Linux(centos)安装nginx

Linux(centos)安装nginx 转载请注明出处https://www.cnblogs.com/funnyzpc/p/13913023.html 注意，本教程安装环境为ce…

大数据 2023年6月3日
0130
• #### 基于docker 安装的mysql 来安装 hive

大数据 2023年11月13日
0110
• #### hive sql 和 spark sql的区别

大数据 2023年11月14日
0163
• #### java 连接 Sqlite 数据库工具类

一、简介 sqlite3非常小，轻量级，就几百K大小；不需要用户名，密码，直接就可以对数据库进行操作。 二、安装sqlite3 1.安装sqlite3 sudo apt-get i…

大数据 2023年11月11日
0127
• #### 使用 Transformers 在你自己的数据集上训练文本分类模型

之前只闻 transformers 超厉害超好用，但是没有实际用过。之前涉及到 bert 类模型都是直接手写或是在别人的基础上修改。但这次由于某些原因，需要快速训练一个简单的文本分…

大数据 2023年5月28日
0142
• #### Linux 网桥实现和网络诊断工具

网桥：工作方式与交换机相同的硬件。 [En] Bridge: hardware that works the same as a switch.网桥内部有一个缓存，里面放了接口和m…

大数据 2023年5月27日
0178
• #### hive初次启动问题

大数据 2023年11月15日
0155
• #### 【Python 基础 2022 最新】练习 2

【Python 基础 2022 最新】练习 2 原创 我是小白呀2022-06-26 01:38:27©著作权 文章标签 python 开发语言 sed 零基础 文章分类 Hado…

大数据 2023年5月26日
0143
• #### sarama的消费者组分析、使用

kafka的go客户端，使用最多的应该是sarama，但以前老的sarama版本不支持消费者组的消费方式，所以大多数人都用sarama-cluster。 后来sarama支持了消费…

大数据 2023年6月3日
0158
• #### Linux下如何正确停止重启启动redis服务

大数据 2023年11月16日
0106
• #### numpy常用用法总结

numpy 简介 各种用法介绍 首先是numpy中的数据类型，ndarray类型，和标准库中的array.array并不一样。 ndarray.ndimthe number of …

大数据 2023年6月3日
0155
• #### Failed to create Spark client for Spark session/30041Code

大数据 2023年11月16日
0184
• #### 如何搭建清晰易懂的数据看板？

更多技术交流、求职机会、试用福利，欢迎关注 字节跳动数据平台微信公众号，回复【1】进入官方交流群 看板/仪表盘/Dashboard是数据分析结果的呈现。用于向读者传达有效的数据信息…

大数据 2023年6月2日
0145
• #### AI场景存储优化：云知声超算平台基于 JuiceFS 的存储实践

云知声是一家专注于语音及语言处理的技术公司。 Atlas 超级计算平台是云知声的计算底层基础架构，为云知声在 AI 各个领域（如语音、自然语言处理、视觉等）的模型迭代提供训练加速等…

大数据 2023年6月3日
0183
• #### centos解决 pip is configured with locations that require TLS/SSL, however the ssl module in Python is not available.

二、编译安装 进入openssl-OpenSSL_1_1_1d 指定安装路径并编译 三、替换当前系统的旧版本 openssl 「先保存原来的」 四、最后查看当前系统 openssl…

大数据 2023年6月3日
0182
• #### 剑指Offer:链表中倒数第 K 个结点(22)

题目描述: 输入一个链表，输出该链表中倒数第k个结点。 解题思路: 设链表的长度为 N。设置两个指针 P1 和 P2，先让 P1 移动 K 个节点，则还有 N – K …

大数据 2023年6月3日
0151