Problem statement

https://leetcode.com/problems/longest-word-in-dictionary/

Solution

Straightforward solution is just to check for each string all prefixes with $O(\sum\limits_i^n w_i^2)$ solution, where w1, w2, ... wn are lengths of our words. We can do better if we sort our words before by length and then iterate from shortest to longest.

Complexity

Time complexity is $O(n\log n \overline{w} + \sum\limits_i^n w_i)$. We need to use key (-len(s), s), because in the end we want to return the longest word with smallest lexicographical order.

Code

class Solution:
    def longestWord(self, words):
        d = defaultdict(int)
        words_set = set(words)
        words.sort(key = lambda s: (-len(s), s))
        for word in words[::-1]:
            if len(word) > 1 and word[:-1] in words_set:
                d[word] = d[word[:-1]] + 1
            elif len(word) == 1:
                d[word] = 1
            else:
                d[word] = 0
                
        for word in words:
            if d[word] == len(word): return word

Remark

Actually we can remove $O(n\log n\overline{w})$ time if we use Tries to sort our words. Alternatively we can put all words in Trie and then traverse it, using dfs.

I saw very similar hard problem with different constraints, but I do not remember its number.