720.词典中最长的单词.md

720. 词典中最长的单词

题目传送门

点击这里

解题思路

这道题根据题意不难想到是要使用字典树来做，字典树的构造是从根节点开始做插入，假设字符串数组[abcd abed acd]，从a开始插入，插入一个b和c，然后b再向下插入c和e，以此方法向下继续，直到插入完，将标志位置为true，这个思路和搜索引擎和路由匹配的规则很类似。建立好后只需要做查找即可，这道题题干的要求是由其他单词逐步增加添加一个字母组成的，所以每到一个树节点标志位都要为true，即该字符在数组中。

代码

type Tree struct {
    children [26]*Tree
    isWord bool
}

// 构建字典树
func (t *Tree) Insert(word string) {
    n := t
    for _, v := range word {
        if n.children[v-'a'] == nil {
            n.children[v-'a'] = &Tree{}
        }
        n = n.children[v-'a']
    }
    n.isWord = true 
}

func (t *Tree) Find(word string) bool {
    n := t
    for _, v := range word {
        if n.children[v-'a'] == nil || !n.children[v-'a'].isWord { // 要逐步添加一个单词，所以每一个isWord都应该是true
            return false
        }
        n = n.children[v-'a']
    }
    return true
}

func longestWord(words []string) string {
    var res string
    t := &Tree{}
    for _, v := range words {
        t.Insert(v)
    }
    for _, v := range words {
        if t.Find(v) && ((len(v) > len(res)) || (len(v) == len(res) && v < res)) {
            res = v
        }
    }
    return res
}