# Leetcode - Longest Word in Dictionary

violet posted @ Mar 28, 2020 06:32:39 AM in 算法 with tags Algorithm Golang Trie , 358 阅读

https://leetcode.com/problems/longest-word-in-dictionary/

Given a list of strings `words` representing an English Dictionary, find the longest word in `words` that can be built one character at a time by other words in `words`. If there is more than one possible answer, return the longest word with the smallest lexicographical order.

If there is no answer, return the empty string.

```Input:
words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]
Output: "apple"
Explanation:
Both "apply" and "apple" can be built from other words in the dictionary. However, "apple" is lexicographically smaller than "apply".```

YATP.

```func longestWord(words []string) string {
root := buildTrie(words)
maxCount := math.MinInt32
result := ""
for _, w := range words {
count := searchTrie(root, w)
if count > maxCount {
maxCount = count
result = w
}
if count == maxCount {
result = min(result, w)
}
}

return result
}

func min(a, b string) string{
if a < b {
return a
}
return b
}

type Trie struct {
Val string
Children []*Trie
}

func buildTrie(words []string) *Trie {
root := &Trie{
Children: make([]*Trie, 26),
}
for _, w := range words {
node := root
for i := 0; i < len(w); i++ {
index := w[i] - 'a'
if node.Children[index] == nil {
node.Children[index] = &Trie{
Children: make([]*Trie, 26),
}
}
node = node.Children[index]
}
node.Val = w
}
return root
}

func searchTrie(root *Trie, word string) int {
node := root
count := 0
for i := 0; i < len(word); i++ {
index := word[i] - 'a'
node = node.Children[index]
if node.Val != "" {
count++
} else {
return count
}
}
return count
}```
Sep 25, 2021 08:27:05 PM

Interesting selection of topic for studying the course of coding.

Escorts in Assam 说:
Sep 25, 2021 08:28:21 PM

They are the beauty of nature. Just follow them.

(输入验证码)
or Ctrl+Enter