Word Search
2024-09-15 13:04:17
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.
For example,
Given board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
word = "ABCCED"
, -> returns true
,
word = "SEE"
, -> returns true
,
word = "ABCB"
, -> returns false
.
分析: 刚开始做的时候有误解,实际上就是从矩阵中找一条线路求解出word dfs求解最方便,注意一下边界范围
class Solution {
private:
int rows;
int cols;
public:
bool exist(vector<vector<char>>& board, string word) {
rows = board.size();
cols = board[].size();
for(int i=; i< rows; i++)
for(int j=;j<cols; j++){
if(dfs(board,i,j,word,))
return true;
}
return false;
}
bool dfs(vector<vector<char>>& board, int x, int y,string word, int index){
//cout << x << " "<<y <<endl;
//cout << "index = "<<index<<endl;
if(x< || y< || x>=rows || y>=cols || (index<word.size() && board[x][y]!=word[index]) )
return false;
if(index+ == word.size()){
return true;
}
char c =board[x][y];
board[x][y] = '.';
if(dfs(board,x-,y,word,index+) || dfs(board,x+,y,word,index+)
|| dfs(board,x,y-,word,index+) || dfs(board,x,y+,word,index+))
return true; board[x][y] =c; return false;
}
};
最新文章
- iOS-APP提交上架流程(新手必看!2016年3月1日最新版)
- SpringMVC 自动封装枚举类的方法
- AngularJs基础(一)
- css3之转换
- HttpClient读取ASP.NET Web API错误信息的简单方法
- Cocos2d-x 2.x项目创建
- eclipse里添加类似myeclipse打开当前操作目录
- Android的读写文件权限
- FZU 2122 又见LKity(KMP+返回所有匹配位置)
- 使用xcrun打包iOS应用
- ABP官方文档翻译 4.1 应用服务
- python 正则表达式Re
- Docker 新手入门
- 学习笔记—CSS基础
- css实现图片等比例缩放
- DataTable转list时 可空类型的转换问题
- c++11新标准for循环和lambda表达式
- Maven Archetype简介以及搭建
- 提升PHP安全:8个必须修改的PHP默认配置
- MySQL 快速构造一亿条记录的表