首页 > 代码库 > 【LeetCode】Word Search
【LeetCode】Word Search
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
.
这题很显然需要DFS,而且递归在leetcode里基本上是TLE的,所以以下就是非递归的DFS。
核心思想如下:
用栈记录当前搜索的路径。
栈存放的节点包括4个成员:x,y坐标,word中的index,已遍历方向dir。
注意dir是非常重要的,用来记录已遍历过的方向(按照上下左右的顺序),不然的话就会出现无限循环的同一节点进栈出栈。
进栈之后的节点置为‘*‘,以免同一节点多次进栈。
出栈之后的节点恢复为word[index]。
其余DFS细节不赘述了,看代码就行。
class Solution { public: struct grid { int x; int y; int index; //在word中的index int dir; //记录已遍历方向,用于回溯 0-无,1-上,2-下,3-左,4-右 }; bool exist(vector<vector<char> > &board, string word) { stack<grid> stk; if(word.size() == 0) return true; int row = board.size(); int col; for(int i = 0; i < row; i ++) { col = board[i].size(); for(int j = 0; j < col; j ++) { if(board[i][j] == word[0]) { grid g; g.x = i; g.y = j; g.index = 0; g.dir = 0; stk.push(g); board[i][j] = ‘*‘; } while(!stk.empty()) { int x = stk.top().x; int y = stk.top().y; int index = stk.top().index; int dir = stk.top().dir; if(index == word.size()-1) { while(!stk.empty()) { int x = stk.top().x; int y = stk.top().y; int index = stk.top().index; int dir = stk.top().dir; board[x][y] = word[index]; stk.pop(); } return true; } if(x-1>=0 && board[x-1][y] == word[index+1] && dir == 0) { stk.top().dir = 1; grid g; g.x = x-1; g.y = y; g.index = index+1; g.dir = 0; stk.push(g); board[x-1][y] = ‘*‘; } else if(x+1<row && board[x+1][y] == word[index+1] && dir <= 1) { stk.top().dir = 2; grid g; g.x = x+1; g.y = y; g.index = index+1; g.dir = 0; stk.push(g); board[x+1][y] = ‘*‘; } else if(y-1>=0 && board[x][y-1] == word[index+1] && dir <= 2) { stk.top().dir = 3; grid g; g.x = x; g.y = y-1; g.index = index+1; g.dir = 0; stk.push(g); board[x][y-1] = ‘*‘; } else if(y+1<board[x].size() && board[x][y+1] == word[index+1] && dir <= 3) { stk.top().dir = 4; grid g; g.x = x; g.y = y+1; g.index = index+1; g.dir = 0; stk.push(g); board[x][y+1] = ‘*‘; } else { int x = stk.top().x; int y = stk.top().y; int index = stk.top().index; board[x][y] = word[index]; stk.pop(); } } } } return false; } };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。