当前位置: 首页> 游戏> 评测 > pageadmin好用吗_展厅设计用什么软件_青岛网站快速排名优化_关键词快速排名平台

pageadmin好用吗_展厅设计用什么软件_青岛网站快速排名优化_关键词快速排名平台

时间:2025/7/10 4:03:23来源:https://blog.csdn.net/weixin_72492465/article/details/144043221 浏览次数:0次
pageadmin好用吗_展厅设计用什么软件_青岛网站快速排名优化_关键词快速排名平台

给定一个 m x n 二维字符网格 board 和一个单词(字符串)列表 words, 返回所有二维网格上的单词 。

单词必须按照字母顺序,通过 相邻的单元格 内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。

这里我们需要在字符表中查找words中的单词,如果我们暴力搜索,然后再去检验的化,效率很低,并且每个点都需要搜索所以行不通
这里我们直接建立words的Trie 然后dfs 建立的Trie 大大减少了dfs的范围

Trie节点Trienode 

这里使用map<char,Tirenode*>内存确实效率更好

struct Tirenode
{unordered_map<char,Tirenode*> next;string s="";                       //标记单词 
};

 Trie节点的添加

 void insert_(string& word){                auto node=this->root;     //遍历节点for(auto c:word){if(!node->next.count(c)) node->next[c]=new Tirenode();  node=node->next[c];}node->s=word; //标记单词}

dfs查找

 我们已经将words的单词假如到了Trie结构中
 所以我们只要dfs board中的字符看是否能搜索到temp不为空字符的情况即可
 去重的话如果我们搜索到了单词temp则将它置空,表示我们已经push_back过了 

 void dfs(point p,vector<vector<char>>& board,Tirenode* temp){auto [x,y]=p;        //结构化绑定char c=board[x][y];  //记录当前字母if(!temp->next.count(c)) return;  //搜索到尾了 则退出递归//搜索到单词if(temp->next[c]->s!="") {dp.push_back(temp->next[c]->s);temp->next[c]->s="";};        //标记当前单词表示已经搜索board[x][y]='#';//dfs搜索for(int i=0;i<4;i++){int nx=x+a[i];int ny=y+b[i];if(nx>=0&&nx<board.size()&&ny>=0&&ny<board[0].size()&&board[nx][ny]!='#'){dfs({nx,ny},board,temp->next[c]);}}//回溯board[x][y]=c;}

完整代码: 

class Solution {
public:typedef pair<int,int> point;vector<string> dp;int a[4]={0,0,1,-1};int b[4]={1,-1,0,0};int max_=0;struct Tirenode{unordered_map<char,Tirenode*> next;string s="";};Tirenode* root=new Tirenode();void insert_(string& word){auto node=this->root;for(auto c:word){if(!node->next.count(c)) node->next[c]=new Tirenode();node=node->next[c];}node->s=word;}void dfs(point p,vector<vector<char>>& board,Tirenode* temp){auto [x,y]=p;char c=board[x][y];if(!temp->next.count(c)) return;if(temp->next[c]->s!="") {dp.push_back(temp->next[c]->s);temp->next[c]->s="";};board[x][y]='#';for(int i=0;i<4;i++){int nx=x+a[i];int ny=y+b[i];if(nx>=0&&nx<board.size()&&ny>=0&&ny<board[0].size()&&board[nx][ny]!='#'){dfs({nx,ny},board,temp->next[c]);}}board[x][y]=c;}vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {for(auto s:words)  insert_(s);  int m=board.size();int n=board[0].size();for(int i=0;i<m;i++){for(int j=0;j<n;j++){dfs({i,j},board,this->root);}}return dp;}
};

关键字:pageadmin好用吗_展厅设计用什么软件_青岛网站快速排名优化_关键词快速排名平台

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: