leetcode212. 单词搜索 II

思路

先将单词为建立trie树，然后从每个位置开始搜索。

const int N=1e4;
class Solution {
public:
    int son[N][26],cnt[N],idx;
    int dx[4]={1,0,-1,0};
    int dy[4]={0,1,0,-1};
    vector<string>ans;
    void insert(string words){//trie树插入操作
        int p=0;
        for(int i=0;i<words.size();i++){
            int x=words[i]-'a';
            if(son[p][x]==0)son[p][x]=++idx;
            p=son[p][x];
        }
        cnt[p]++;//cnt[p]表示这个位置的单词个数
    }
    void dfs(int i,int j,vector<vector<char>>& board,string path,int curidx){
        char ch=board[i][j];
        int t=ch-'a';
        if(ch=='#'||son[curidx][t]==0)return ;
        curidx=son[curidx][t];
        if(cnt[curidx]>=1) {//当前位置有单词
            ans.push_back(path+ch);
            cnt[curidx]=0;//置0去重
        }
        board[i][j]='#';//该位置已访问
        for(int m=0;m<4;m++){
            int x=i+dx[m],y=j+dy[m];
            if(x>=0&&x<board.size()&&y>=0&&y<board[0].size())
                dfs(x,y,board,path+ch,curidx);
        }
        board[i][j]=ch;//回溯
        return ;
    }
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        //初始化
        memset(son,0,sizeof son);
        memset(cnt,0,sizeof cnt);
        idx=0;
        //建立trie树
        for(auto w:words){
            insert(w);
        }
        for(int i=0;i<board.size();i++)
            for(int j=0;j<board[0].size();j++)
                dfs(i,j,board,"",0);
    
        return ans;
    }
};