回溯法
- 单词搜索
- 单词搜索||
单词搜索 【题目】
给定一个二维网格和一个单词，找出该单词是否存在于网格中。【思路】
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
文章图片
【代码】
class Solution {
public:
int dir[4][4]={{-1,0},{1,0},{0,-1},{0,1}};
//位置坐标
bool dfs(int x,int y,int index,vector>& board,string &word,vector>& visited)
{
if(index==word.size()-1)
return word[index]==board[x][y];
if(word[index]==board[x][y])
{
visited[x][y]=true;
for(int i=0;
i<4;
i++)
{
int new_x=x+dir[i][0];
int new_y=y+dir[i][1];
if(new_x>=0&&new_x=0&&new_y>& board, string word) {
int m=board.size();
//行数
int n=board[0].size();
//列数
vector> visited(m,vector(n));
for(int i=0;
i 单词搜索|| 【题目】
给定一个二维网格 board 和一个字典中的单词列表 words，找出所有同时在二维网格和字典中出现的单词。示例:
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。
输入:
words = [“oath”,“pea”,“eat”,“rain”] and board =
[
[‘o’,‘a’,‘a’,‘n’],
[‘e’,‘t’,‘a’,‘e’],
[‘i’,‘h’,‘k’,‘r’],
[‘i’,‘f’,‘l’,‘v’]
]
输出: [“eat”,“oath”]
【思路】
在|版本上增加代码代码，如下：
vector> findWords(vector>& board, vector>& words)
{
vector>res;
for(int i=0;
i 结果正确但是超时。
文章图片
文章图片
需要解决问题：
文章图片
【改进】
前缀树，代码摘自一个大佬，做了相关注释
【注释】
文章图片
【代码】
class TrieNode{
public:
string word = "";
vector nodes;
TrieNode():nodes(26, 0){}
};
class Solution {
int rows, cols;
vector> res;
public:
vector> findWords(vector>& board, vector>& words) {
rows = board.size();
cols = rows ? board[0].size():0;
if(rows==0 || cols==0) return res;
//建立字典树的模板
TrieNode* root = new TrieNode();
for(string word:words){
TrieNode *cur = root;
for(int i=0;
inodes[idx]==0) cur->nodes[idx] = new TrieNode();
cur = cur->nodes[idx];
}
cur->word = word;
}//DFS模板
for(int i=0;
i>& board, TrieNode* root, int x, int y){
char c = board[x][y];
//递归边界
if(c=='.' || root->nodes[c-'a']==0) return;
root = root->nodes[c-'a'];
if(root->word!=""){
res.insert(res.begin(),root->word);
root->word = "";
}board[x][y] = '.';
if(x>0) dfs(board, root, x-1, y);
if(y>0) dfs(board, root, x, y-1);
if(x+1 【力扣 79.单词搜索+212.单词搜索II】【结果】
文章图片
推荐阅读
- 数据结构与算法|【算法】力扣第 266场周赛
- leetcode|今天开始记录自己的力扣之路
- Python|Python 每日一练 二分查找 搜索旋转排序数组 详解
- 【LeetCode】28.实现strstr（） （KMP超详细讲解，sunday解法等五种方法，java实现）
- LeetCode-35-搜索插入位置-C语言
- leetcode python28.实现strStr()35. 搜索插入位置
- Leetcode Permutation I & II
- python|leetcode Longest Substring with At Most Two Distinct Characters 滑动窗口法
- LeetCode 28 Implement strStr() (C,C++,Java,Python)
- Python|Python Leetcode(665.非递减数列)