地址

https://leetcode.com/problems/word-search-ii/

题目

Given a 2D board and a list of words from the dictionary, find all words in the board.

Each word must be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

Example:

Input: 
board = [
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]
words = ["oath","pea","eat","rain"]

Output: ["eat","oath"]

Note:

1. All inputs are consist of lowercase letters a-z.
2. The values of words are distinct.

思路

leetcode的题就这点不好，不告诉你数据范围，也不告诉你时间和空间限制。算法写完了才发现TLE，真的是有毒。

这题正解Trie树+dfs，一开始我没写Trie树，直接dfs+一堆trick，然后果然TLE。

加不加Trie树，时间复杂度就是多个O(k)的区别，k是words的数量。

acm题刷多了后，看到不给数据范围的题真的难受。acm要是遇到数据范围小的题目，直接暴力完事了，不需要想其他解法

代码

#define MAXNUM 26
//定义字典树结构体
typedef struct Trie
{
    int flag;  //从根到此是否为一个单词
    Trie *next[MAXNUM];
}Trie;
//声明一个根
Trie *root;
//初始化该根
void init()
{
    root = (Trie *)malloc(sizeof(Trie));
    root->flag=0;
    for(int i=0;i<MAXNUM;i++)
    root->next[i]=NULL;
}
//对该字典树的插入单词操作
void insert(const char *word, int id)
{
    Trie *tem = root;
    while(*word!='\0')
    {
        if(tem->next[*word-'a']==NULL)
        {
            Trie *cur = (Trie *)malloc(sizeof(Trie));
            for(int i=0;i<MAXNUM;i++)
            cur->next[i]=NULL;
            cur->flag=0;
            tem->next[*word-'a']=cur;
        }
        tem = tem->next[*word-'a'];
        word++;
    }
    tem->flag=id;
}
//查询一个单词的操作
bool search(char *word)
{
    Trie *tem = root;
    for(int i=0;word[i]!='\0';i++)
    {
        if(tem==NULL||tem->next[word[i]-'a']==NULL)
        return false;
        tem=tem->next[word[i]-'a'];
    }
    return tem->flag;
}
//释放字典树内存操作，由于本题测试数据后程序自动跳出，所以这里没写释放内存函数
void del(Trie *cur)
{
    for(int i=0;i<MAXNUM;i++)
    {
        if(cur->next[i]!=NULL)
        del(cur->next[i]);
    }
    free(cur);
}


class Solution {
public:
    int dx[4] = {0, 0, -1, 1}, dy[4] = {-1, 1, 0, 0};
    int vis[1000][1000];
    int n, m;
    bool ok[100000];
    vector<string>ans;
    
    vector<string> findWords(vector<vector<char>>& mp, vector<string>& words) {
        n = mp.size(), m=mp[0].size();
        init();
        memset(ok, 0, sizeof ok);
        memset(vis, 0, sizeof vis);
        for(int i=0;i<words.size(); ++i)
            insert(words[i].c_str(), i+1);
        for(int i=0;i<n;++i)
        for(int j=0;j<m;++j)
        if(root->next[mp[i][j]-'a'] != NULL)
            dfs(i, j, root->next[mp[i][j]-'a'], mp);
        for(int i=0;i<words.size(); ++i)
        if(ok[i])
            ans.push_back(words[i]);
        return ans;
    }
    
    void dfs(int x, int y, Trie* cur, vector<vector<char>>& mp)
    {
        if(cur->flag > 0)
            ok[cur->flag - 1] = 1;
        vis[x][y]=1;
        for(int i=0;i<4;++i)
        {
            int nx=x+dx[i], ny = y + dy[i];
            if(nx>-1 && ny>-1 && nx<n && ny<m && !vis[nx][ny]  && cur->next[mp[nx][ny]-'a'] != NULL)
                dfs(nx, ny, cur->next[mp[nx][ny]-'a'], mp);
        }
        vis[x][y] = 0;
    }
    
    
};