[Python] 3 solutions: BFS, Sorting, TrieNode - Clean & Concise
\u2714\uFE0F Solution 1: BFS\n- Same idea with 127. Word Ladder\npython\nclass Solution:\n    def longestWord(self, words: List[str]) -> str:\n        wordSet =
**\u2714\uFE0F Solution 1: BFS**\n- Same idea with [127. Word Ladder](https://leetcode.com/problems/word-ladder/)\n```python\nclass Solution:\n    def longestWord(self, words: List[str]) -> str:\n        wordSet = set(words)\n        q = deque([""])\n        ans = ""\n        while q:\n            word = q.popleft()\n            if len(word) > len(ans):\n                ans = word\n                \n            for c in ascii_lowercase:\n                newWord = word + c\n                if newWord in wordSet:\n                    q.append(newWord)\n                    wordSet.remove(newWord)\n                    \n        return ans\n```\n**Complexity**\n- Time: `O(27N * M)`, where `N <= 1000` is length of `words`, `M <= 30` is length of each word.\n   Explain: BFS takes `O(E+V)`, where `V` is number of vertices = number of words in the dictionary, `E = 26V` is number of edges (because each vertice there is up to 26 neighbors). Each time, the cost to build new string is `O(M)`.\n   So total time complexity is `O(27N * M)`.\n- Space: `O(N * M)`\n\n---\n\n**\u2714\uFE0F Solution 2: Sorting**\n- Sort the `words` alphabetically, therefore shorter words always comes before longer words.\n- Along the sorted list, populate the words that can be built.\n- Any prefix of a word must comes before that word.\nCredit the idea from @alexander under this post [Java/C++ Clean Code](https://leetcode.com/problems/longest-word-in-dictionary/discuss/109114)\n\n```python\nclass Solution:\n    def longestWord(self, words: List[str]) -> str:\n        words.sort()\n        seen = set([""])\n        ans = ""\n        for word in words:\n            if word[:-1] in seen:\n                seen.add(word)\n                if len(word) > len(ans):\n                    ans = word\n        return ans\n```\n**Complexity**\n- Time: `O(NlogN * M)`, where `N <= 1000` is length of `words`, `M <= 30` is length of each word.\n- Space: `O(N * M)`\n\n---\n\n**\u2714\uFE0F Solution 3: Trie Node**\n```python\nclass TrieNode:\n    def __init__(self):\n        self.children = defaultdict(TrieNode)\n        self.word = None\n    def addWord(self, word):\n        cur = self\n        for c in word:\n            cur = cur.children[c]\n        cur.word = word\n\nclass Solution:\n    def longestWord(self, words: List[str]) -> str:\n        trieRoot = TrieNode()\n        for word in words:\n            trieRoot.addWord(word)\n            \n        ans = ""\n        bfs = deque([trieRoot])\n        while bfs:\n            cur = bfs.popleft()\n            for child in cur.children.values():\n                if child.word != None:\n                    if len(child.word) > len(ans) or len(child.word) == len(ans) and child.word < ans:\n                        ans = child.word\n                    bfs.append(child)\n        return ans\n```\n**Complexity**\n- Time: `O(N * M)`, where `N <= 1000` is length of `words`, `M <= 30` is length of each word.\n- Space: `O(N * M)`
[]