最长单词

给定一组单词 words，编写一个程序，找出其中的最长单词，且该单词由这组单词中的其他单词组合而成。若有多个长度相同的结果，返回其中字典序最小的一项，若没有符合要求的单词则返回空字符串。

  • 输入： [“cat”,”banana”,”dog”,”nana”,”walk”,”walker”,”dogwalker”]
    输出： “dogwalker”
    解释： “dogwalker”可由”dog”和”walker”组成。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
var longestWord = function(words) {
    words.sort((a, b) => {
        if (!(a.length - b.length)) {
            return a < b ? 1 : -1
        }
        return a.length - b.length;
    });
    const m = new Map();
    words.forEach(item => {
        const v = m.has(item[0]) ? m.get(item[0]) : [];
        v.push(item);
        m.set(item[0], v);
    })
    for (let i = words.length - 1; i >= 0; i--) {
        const v = m.get(words[i][0]);
        v.splice(v.indexOf(words[i]), 1);
        m.set(words[i][0], v);
        if (dfs(words[i])) {
            return words[i]
        }
    }
    return '';
    function dfs(v) {
        if (!v) {
            return true;
        }
        if (!m.has(v[0])) {
            return false;
        }
        for (let item of m.get(v[0])) {
            const n = item.length;
            if (v.slice(0, n) === item) {
                 if(dfs(v.slice(n))){
                     return true;
                 }
            }
        }
        return false;
    }
};