【LeetCode】79. Word Search
LeetCode word search 79
2023-09-11 14:20:27 时间
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[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; } };
相关文章
- 通过 LeetCode 周赛学习二分查找算法
- Word 通过添加Package 实现word藏毒
- Leetcode: Shortest Word Distance
- Leetcode: Implement Queue using Stacks
- Leetcode: Substring with Concatenation of All Words
- Word控件Spire.Doc 【文本】教程(10) ;在 word 文档中的字符或句子周围应用边框
- Word控件Spire.Doc 【超链接】教程(3):在C#中查找word文档中的超链接
- Word控件Spire.Doc 转换教程(二十二): 将word文档中的隐藏文本保存为PDF
- Word控件Spire.Doc 转换教程(二十二): 将word文档中的隐藏文本保存为PDF
- 【Leetcode】691. 贴纸拼词(困难)
- 97、【树与二叉树】leetcode ——513.找树左下角的值:层次遍历+回溯法(C++版本)
- SpringBoot+Poi-tl根据Word模板动态生成word(含动态行表格、合并单元格)
- 【LeetCode】92. Reverse Linked List II
- leetcode先刷_Pascal's Triangle II
- [LeetCode] 1091. Shortest Path in Binary Matrix 二进制矩阵中的最短路径
- [LeetCode] Most Common Word 最常见的单词
- [LeetCode] 298. Binary Tree Longest Consecutive Sequence 二叉树最长连续序列
- [LeetCode] 244. Shortest Word Distance II 最短单词距离之二
- [LeetCode] 212. Word Search II 词语搜索之二
- [LeetCode] 29. Divide Two Integers 两数相除
- [LeetCode] 129. Sum Root to Leaf Numbers 求根到叶节点数字之和
- leetcode 139. Word Break 单词拆分(中等)
- leetcode 524. Longest Word in Dictionary through Deleting 通过删除字母匹配到字典里最长单词