Longest Word in Dictionary — Trie BFS/DFS

Problem

Given a list of words, find the longest word where all its prefixes exist in the list.

Solutions

Python

class Solution:
    def longestWord(self, words: list[str]) -> str:
        trie={}
        for w in words:
            node=trie
            for c in w:
                if c not in node: node[c]={}
                node=node[c]
            node['#']=w
        ans=""
        stack=[trie]
        while stack:
            node=stack.pop()
            for c,child in node.items():
                if c=='#': continue
                if '#' in child:
                    w=child['#']
                    if len(w)>len(ans) or (len(w)==len(ans) and w<ans): ans=w
                    stack.append(child)
        return ans

Complexity

Time: O(total chars) | Space: O(total chars)