720.词典中最长的单词
720.词典中最长的单词
题解
第一种：用map存前缀，就可以判断当前单词是否能够符合条件了
第二种：字典树golang力扣leetcode 208.实现Trie(前缀树）,在该模板上变一下即可，即查询的时候，每个字母的isEnd都要是true，题目要求就是这样
代码
1
func longestWord1(words []string) string { sort.Slice(words, func(i, j int) bool { return len(words[i]) < len(words[j]) || len(words[i]) == len(words[j]) && words[i] > words[j] //为什么这里是字典序大的排前面，是为了后面ans=v的时候，不用在判断了，如果两个单词都成立的时候，字典序小会覆盖之前的赋值 }) ans := "" mp := make(map[string]bool) mp[""] = true for _, v := range words { preWord := v[:len(v)-1] //该单词去掉最后一个字母 abc-->ab if _, ok := mp[preWord]; ok { ans = v mp[v] = true //如果前缀字母出现了，则这个单词也可以成立 } } return ans }
2
type Trie struct { children [26]*Trie //当前字母的下一个字母是26个字母之一 isEnd bool //某个单词以当前字母结尾 } func Constructor() Trie { return Trie{} } func (t *Trie) Insert(word string) { node := t //从根出发 for _, ch := range word { ch -= 'a' if node.children[ch] == nil { //如果这个字母不存在 node.children[ch] = &Trie{} //则新建这个字母 } node = node.children[ch] //下一个字母从这个字母的位置开始找 } node.isEnd = true //所有字母都插入完了，把最后一个字母的结束标志置为true } func (t *Trie) Search(word string) bool { node := t //从根出发 for _, ch := range word { ch -= 'a' if node.children[ch] != nil && node.children[ch].isEnd == true { node = node.children[ch] //下一个字母从这个字母的位置开始找 } else { //如果这个字母不存在 或者 不以该字母结尾，则不成立 return false } } return true } func longestWord(words []string) (longest string) { t := &Trie{} for _, word := range words { t.Insert(word) } for _, word := range words { if t.Search(word) && (len(word) > len(longest) || len(word) == len(longest) && word < longest) { longest = word } } return longest }
