Leetcode - Longest Word in Dictionary

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
}

• 相关文章
• 全局相关文章