LeetCode 212. Word Search II

题目

题意:给你一个字母组成的矩阵,和一些单词,问你在矩阵中能否找到这些单词。

题解:这道题目的数据范围大概是,单词很多!矩阵倒不大。这么多单词,一个一个拿来暴搜肯定超时,把他们变成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);        }  };