【LeetCode】79. Word Search
2024-10-20 09:36:30
Word Search
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里基本上是TLE的,所以以下就是非递归的回溯。
核心思想如下:
用栈记录当前搜索的路径。
栈存放的节点包括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[].empty())
return false;
int m = board.size();
int n = board[].size(); for(int i = ; i < m; i ++)
{
for(int j = ; j < n; j ++)
{
if(board[i][j] == word[])
{// maybe a success
stack<Node> stk;
Node curnode(word[], i, j, );
stk.push(curnode);
board[curnode.x][curnode.y] = '*';
int wind = ;
if(wind == word.size())
return true;
while(!stk.empty())
{
if(stk.top().p == )
{
stk.top().p = ;
if(stk.top().x > && board[stk.top().x-][stk.top().y] == word[wind])
{
Node nextnode(word[wind], stk.top().x-, stk.top().y, );
stk.push(nextnode);
board[nextnode.x][nextnode.y] = '*';
wind ++;
if(wind == word.size())
return true;
continue;
}
}
if(stk.top().p == )
{
stk.top().p = ;
if(stk.top().x < m- && board[stk.top().x+][stk.top().y] == word[wind])
{
Node nextnode(word[wind], stk.top().x+, stk.top().y, );
stk.push(nextnode);
board[nextnode.x][nextnode.y] = '*';
wind ++;
if(wind == word.size())
return true;
continue;
}
}
if(stk.top().p == )
{
stk.top().p = ;
if(stk.top().y > && board[stk.top().x][stk.top().y-] == word[wind])
{
Node nextnode(word[wind], stk.top().x, stk.top().y-, );
stk.push(nextnode);
board[nextnode.x][nextnode.y] = '*';
wind ++;
if(wind == word.size())
return true;
continue;
}
}
if(stk.top().p == )
{
stk.top().p = ;
if(stk.top().y < n- && board[stk.top().x][stk.top().y+] == word[wind])
{
Node nextnode(word[wind], stk.top().x, stk.top().y+, );
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;
}
};
最新文章
- 7 -- Spring的基本用法 -- 6...
- C#中的new修饰符
- JVM的垃圾回收机制详解和调优
- SQL..如何用命令删除数据库中所有的表?
- android AlarmManager 详解
- WPF学习02:Routed Events
- json,serialze之格式
- controller.pp 各组件的安装顺序
- UGUI学习之InputField
- 【Android】Intent中使用Extra传递数据
- Realview MDK 中不用手动开中断的原因
- Dojo实现Tabs页报错(二)
- robotium问答
- ssh别名登录密钥登录
- TCP/IP协议 数据链路层
- 转发 ---->; 2018年阿里巴巴重要开源项目汇总(持续更新中)
- h5微信支付在微信内页使用微信公众号支付
- Django模版基本标签详解
- unity之UI
- JQuery控制radio选中和不选中方法总结