LeetCode 212. Word Search II
- 2020 年 2 月 14 日
- 筆記
题意:给你一个字母组成的矩阵,和一些单词,问你在矩阵中能否找到这些单词。
题解:这道题目的数据范围大概是,单词很多!矩阵倒不大。这么多单词,一个一个拿来暴搜肯定超时,把他们变成hash 效率也很低。最好的办法,把这些单词组成一个字典树(前缀树),然后在矩阵里DFS时同时从树上匹配单词。
class Solution { public: map<int,int> tree[100005]; map<int,int> tag[100005]; int vis[1005][1005]; int pos=0; int dir[4][2]={{0,-1},{0,1},{-1,0},{1,0}}; vector<string> ans; int vis2[100005]; int n,m; vector<string> findWords(vector<vector<char>>& board, vector<string>& words) { n=board.size(); if(n==0) return ans; m=board[0].size(); for(int i=0;i<words.size();i++) { fun(words[i],0,0,i+1); } for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { vis[i][j]=1; DFS(i,j,0,board,words); vis[i][j]=0; if(ans.size()==words.size()) break; } } return ans; } void DFS(int x,int y,int k,vector<vector<char>>& map,vector<string>& words) { if(tree[k][map[x][y]]==0) return; int t = tag[k][map[x][y]]; if(t!=0&&vis2[t]==0) { ans.push_back(words[t-1]); vis2[t]=1; } for(int i=0;i<4;i++) { int xx = x+dir[i][0]; int yy = y+dir[i][1]; if(!(xx>=0&&xx<n&&yy>=0&&yy<m)) continue; if(vis[xx][yy]==1) continue; vis[xx][yy]=1; DFS(xx,yy,tree[k][map[x][y]],map,words); vis[xx][yy]=0; } } void fun(string word,int i,int j,int tag1) { if(tree[j][word[i]]==0) { tree[j][word[i]]=++pos; } if(i==word.length()-1) { tag[j][word[i]]=tag1; return; } fun(word,i+1,tree[j][word[i]],tag1); } };