Problem statement

https://leetcode.com/problems/longest-word-with-all-prefixes/

Solution

This problem is almost the same as 0720. Longest Word in Dictionary but with differnt constraints.

One of the ways to solve this problem is to put all words to trie and then traverse it and check we have end_node everywhere in our path. dfs(node) will return the longest word, which start from node.

Complexity

Time complexity to create tree is O(M), where M is total length of all words. More interesting question about dfs. I think it is also O(M) complexity, but I am not 100 percent sure. Space complexity is O(M).

Code

class TrieNode:
    def __init__(self):
        self.children = {}
        self.end_node = 0

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        root = self.root
        for symbol in word:
            root = root.children.setdefault(symbol, TrieNode())
        root.end_node = 1

class Solution:
    def longestWord(self, words):
        trie = Trie()
        for word in words:
            trie.insert(word)
              
        def dfs(node):
            cands = []
            for symb in node.children:
                if node.children[symb].end_node == 1:
                    cands += [symb + dfs(node.children[symb])]
            if not cands: return ""
                    
            return min(cands, key = lambda x: (-len(x), x))
        
        return dfs(trie.root)

Remark

In fact lenght of candidate can not be more than O(sqrt(M)), and I think we can use this somehow.