LeetCode 720. 词典中最长的单词

LeetCode 720. 词典中最长的单词

思路：

这道题应该是mid难度，dfs搜索，建立一个树。

代码：

const int N = 30010;
class Solution {
public:

    int son[N][26];
    int ids[N];
    int idx = 0;

    void insert(string &word,int id){
        int p = 0;
        for(int i = 0;i < word.size();i++){
            auto t = word[i] - 'a';
            if(!son[p][t]) son[p][t] = ++idx;
            p = son[p][t]; 
        }
        ids[p] = id;
    }

    string longestWord(vector<string>& words) {
        memset(ids,-1,sizeof ids);
        memset(son,0,sizeof son);

        for(int i = 0;i < words.size();i++){
            insert(words[i],i);
        }
        //len id
        auto t = dfs(0,0);
        if(t[1] != -1) return words[t[1]];
        return "";
    }

    vector<int> dfs(int len,int p){
        vector<int> res{len,ids[p]};

        for(int i = 0;i < 26;i++){
            int j = son[p][i];
            //存在这个儿子 而且在words中也存在
            if(j && ids[j] != -1){
                auto t = dfs(len + 1,j);
                if(res[0] < t[0]) res = t;
            }
        }
        return res;
    }
};