LC 0720 [M] Longest Word in Dictionary - ALawliet/algorithms GitHub Wiki

this is BFS because we are essentially using the SHORTEST PATH to the longest word

class TrieNode(object):
    def __init__(self):
        self.children = defaultdict(TrieNode)
        self.isEnd = False
        self.word = ''
        
class Trie(object):
    def __init__(self):
        self.root = TrieNode()
        
    def insert(self, word):
        node = self.root
        for c in word:
            node = node.children[c]
        node.isEnd = True
        node.word = word
    
    def bfs(self):
        Q = deque([self.root])
        res = ''
        while Q:
            node = Q.popleft()
            
            for child in node.children.values():
                if child.isEnd:
                    Q.append(child)
                    
                    if len(child.word) > len(res) or child.word < res: # longest word with smallest lexicographical order
                        res = child.word      
        return res
    
class Solution(object):
    def longestWord(self, words):
        trie = Trie()
        
        for w in words:
            trie.insert(w)
            
        return trie.bfs()