720. Longest Word in Dictionary

class Solution:
    def longestWord(self, words: List[str]) -> str:
        """ tc O(NlgL)   sc O(N)
        1. sort by len 
        2. check valid word 
        3. find max length with smallest lexical order 
        """
        words.sort(key= lambda x: len(x))
        valid = set([''])
        for w in words:
            if w[:-1] in valid:
                valid.add(w)
        return min(valid, key = lambda x: (-len(x), x))

class Trie:
    class TrieNode:
        def __init__(self):
            self.children = {}
            self.isEnd = False
            self.word = ''
    def __init__(self):
        self.trie = self.TrieNode()
        
        
    def add(self,w)-> int:
        cur = self.trie
        cnt = 0
        for c in w:
            if c not in cur.children:
                cur.children[c] = self.TrieNode()
            cur = cur.children[c]
        cur.isEnd = True
        cur.word = w
    
    def bfs(self):
        res = ''
        root = self.trie
        q = collections.deque([root])
        while q :
            cur = q.popleft()
            for nxt in cur.children.values():
                if nxt.isEnd:
                    q.append(nxt)
                    # instead of using len(nxt.word) >= len(res) and nxt.word < res, because in bfs, res < word natually 
                    if len(nxt.word) > len(res) or nxt.word < res :
                        res = nxt.word
        return res 
        
    
class Solution:
    def longestWord(self, words: List[str]) -> str:
        """
        tc O(NL + all consecutive words)  sc O(NL + all consecutive words) 
        """
        trie = Trie()
        for w in words:
            trie.add(w)
        return trie.bfs()