LeetCode(79) Word Search
2024-08-30 12:11:31
题目
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 =
[
[“ABCE”],
[“SFCS”],
[“ADEE”]
]
word = “ABCCED”, -> returns true,
word = “SEE”, -> returns true,
word = “ABCB”, -> returns false.
分析
开始采用回溯递归的方法实现,但是LeetCode的测试平台给出一个找不到Search的编译error,很是奇怪,待找到问题,再来更新。
CE代码
class Solution {
public:
bool Search(vector<vector<char> > &board, int &x, int &y, string &word, vector<vector<int> > &isVisited)
{
if (word.empty())
return true;
//当前字符有4个查找方向上、下、左、右
vector<vector<int> > Direction = { { 0, 1 }, { 0, -1 }, { -1, 0 }, { 1, 0 } };
for (size_t i = 0; i < Direction.size(); ++i)
{
//要查找的下一个字符
int xx = x + Direction[i][0];
int yy = y + Direction[i][1];
if (xx >= 0 && yy >= 0 && xx < board.size() && yy < board[xx].size() && isVisited[xx][yy] == 0 && board[xx][yy] == word[0])
{
isVisited[xx][yy] = 1;
if (word.length() == 1 || Search(board, xx, yy, word.substr(1), isVisited))
return true;
isVisited[xx][yy] = 0;
}//if
}//for
return false;
}
bool exist(vector<vector<char>>& board, string word) {
if (board.empty() || board[0].empty())
return false;
if (word.empty())
return true;
int m = board.size();
int n = board[0].size();
vector<vector<int> > isVisited(m, vector<int>(n, 0));
for (int i = 0; i < m; ++i)
{
for (int j = 0; j < n; ++j)
{
if (!word.empty() && board[i][j] == word[0])
{
//修改访问标志为1 代表已访问
isVisited[i][j] = 1;
if (word.length() == 1 || Search(board, i, j, word.substr(1), isVisited))
return true;
//若没有找到目标串,则从下一个字符重新查找,将当前字符访问标志改为0
isVisited[i][j] = 0;
}
}//for
}//for
return false;
}
};
AC代码
此处代码源于参考博客,收益良多,谢谢博主。
其思想是:
用栈记录当前搜索的路径。
栈存放的节点包括4个成员: 字符c, x,y坐标,已遍历方向p。
注意p在回溯法中是非常重要的,用来记录已遍历过的方向(按照上下左右的顺序),不然的话就会出现无限循环的同一节点进栈出栈。
进栈之后的节点置为’*’,以免同一节点多次进栈。
出栈之后的节点恢复为word[wind]。
struct Node
{
char c;
int x;
int y;
int p; //next trial is 0-up, 1-down, 2-left, 3-right
Node(char newc, int newx, int newy, int newp): c(newc), x(newx), y(newy), p(newp) {}
};
class Solution {
public:
bool exist(vector<vector<char> > &board, string word) {
if(board.empty() || board[0].empty())
return false;
int m = board.size();
int n = board[0].size();
for(int i = 0; i < m; i ++)
{
for(int j = 0; j < n; j ++)
{
if(board[i][j] == word[0])
{// maybe a success
stack<Node> stk;
Node curnode(word[0], i, j, 0);
stk.push(curnode);
board[curnode.x][curnode.y] = '*';
int wind = 1;
if(wind == word.size())
return true;
while(!stk.empty())
{
if(stk.top().p == 0)
{
stk.top().p = 1;
if(stk.top().x > 0 && board[stk.top().x-1][stk.top().y] == word[wind])
{
Node nextnode(word[wind], stk.top().x-1, stk.top().y, 0);
stk.push(nextnode);
board[nextnode.x][nextnode.y] = '*';
wind ++;
if(wind == word.size())
return true;
continue;
}
}
if(stk.top().p == 1)
{
stk.top().p = 2;
if(stk.top().x < m-1 && board[stk.top().x+1][stk.top().y] == word[wind])
{
Node nextnode(word[wind], stk.top().x+1, stk.top().y, 0);
stk.push(nextnode);
board[nextnode.x][nextnode.y] = '*';
wind ++;
if(wind == word.size())
return true;
continue;
}
}
if(stk.top().p == 2)
{
stk.top().p = 3;
if(stk.top().y > 0 && board[stk.top().x][stk.top().y-1] == word[wind])
{
Node nextnode(word[wind], stk.top().x, stk.top().y-1, 0);
stk.push(nextnode);
board[nextnode.x][nextnode.y] = '*';
wind ++;
if(wind == word.size())
return true;
continue;
}
}
if(stk.top().p == 3)
{
stk.top().p = 4;
if(stk.top().y < n-1 && board[stk.top().x][stk.top().y+1] == word[wind])
{
Node nextnode(word[wind], stk.top().x, stk.top().y+1, 0);
stk.push(nextnode);
board[nextnode.x][nextnode.y] = '*';
wind ++;
if(wind == word.size())
return true;
continue;
}
}
//restore
board[stk.top().x][stk.top().y] = stk.top().c;
stk.pop();
wind --;
}
}
}
}
return false;
}
};
最新文章
- Job for httpd.service failed because the control process exited with error code. See ";systemctl status httpd.service"; and ";journalctl -xe"; for details
- SQL查询记录是否在另一个表中存在
- 8659 Mine Sweeping
- Culcurse
- TextBox仿Foxmail收件人删除效果
- java double保留小数点的零的问题,java保留小数点问题
- Android View 绘制过程
- android 欢迎界面的淡入效果
- HDU-1372 Knight Moves (BFS)
- oracle数据库导入导出命令!(转)
- Noah的学习笔记之Python篇:装饰器
- CSS3随笔系列之transform(一)—— transform-origin
- LINUX怎么修改IP地址
- 老李分享:Web Services 组件 1
- [Codeforces266E]More Queries to Array...——线段树
- 用HBuilderX 打包 vue 项目 为 App 的步骤
- Java笔记Spring(二)
- Android 中查看内存的使用情况集常用adb命令
- python+win32+ie浏览器操作 TypeError: getElementById() takes exactly 1 argument (2 given)
- dos命令:window10程序控制命令