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); } };
