词典中最长的单词

给出一个字符串数组 words 组成的一本英语词典。返回 words 中最长的一个单词，该单词是由 words 词典中其他单词逐步添加一个字母组成。
若其中有多个可行的答案，则返回答案中字典序最小的单词。若无答案，则返回空字符串。

  • 输入：words = [“w”,”wo”,”wor”,”worl”, “world”]

  • 输出：”world”

  • 解释： 单词”world”可由”w”, “wo”, “wor”, 和 “worl”逐步添加一个字母组成。

  • 输入：words = [“a”, “banana”, “app”, “appl”, “ap”, “apply”, “apple”]

  • 输出：”apple”

  • 解释：”apply” 和 “apple” 都能由词典中的单词组成。但是 “apple” 的字典序小于 “apply”

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var longestWord = function(words) {
    let set = new Set()
    words.forEach(v => set.add(v))//set方便查找
		//先按长度排序，在按字典序
    words.sort((a, b) => a.length === b.length ? a.localeCompare(b) : b.length - a.length)
    for (let i = 0; i < words.length; i++) {
        let flag = true
        for (let j = 1; j < words[i].length; j++) {
            if (!set.has(words[i].substring(0, j))) {//查看set中是否有该字符串的每个子串
                flag = false
                break
            }
        }
        if (flag) {
            return words[i]
        }
    }
    return ''
};