/**
 * @param {string[]} words
 * @return {string}
 */
var longestWord = function(words) {
    totalWords = words.length;
    words.sort(function(a, b) { // Sort by word length
        return a.length - b.length;
    });
    var wordLen = 0;
    var maxLen = words[totalWords-1].length;
    var wordsByLen = new Array(maxLen);
    for (i in words) {
        j = words[i].length - 1;
        wordsByLen[j] = wordsByLen[j] || [];
        wordsByLen[j].push(words[i]);
    };

    wordsByLen2 = new Array(maxLen);
    wordsByLen2[0] = new Set(wordsByLen[0])

    // for (i = 0; i < wordsByLen2.length; i++) {
    for (i = 1; i < wordsByLen2.length; i++) {
        wordsByLen2[i] = new Set();
    }    

    var tryout = function(level, word, arr, arr2) {
        maxLen = arr.length;
        if (level < maxLen - 1) {
            for (j in arr[level+1]) {
                if (word == arr[level+1][j].slice(0, level+1)) {
                    if (!arr2[level+1].has(arr[level+1][j])) {
                        arr2[level+1].add(arr[level+1][j]);
                        tryout(level+1, arr[level+1][j], arr, arr2);
                    }
                }
            }            
        }
    }
    
    for (i in wordsByLen[0]) {
        tryout(0, wordsByLen[0][i], wordsByLen, wordsByLen2);        
    }
    
    if (!wordsByLen2[0]) {
        return "";
    };
    
    var longestWord = "";   
    var word = "";
    for (i = 0; i < wordsByLen2.length; i++) {
        if (wordsByLen2[i]) {
            for (word of wordsByLen2[i]) {
                if (!longestWord || longestWord.length < word.length || longestWord > word) {
                    longestWord = word;
                }
            };
        } else {
            break;
        }        
    }
    
    return longestWord;    
};

class Solution:
    """Given a list of strings words representing an English Dictionary, 
    find the longest word in words that can be built one character at a time by other words in words. 
    If there is more than one possible answer, return the longest word with the smallest lexicographical order."""
    
    def word_prefixes(self, word: str) -> List[str]:
        """Возвращает все префиксы слова (не включает само слово и нулевой префикс)"""
        for last_char_index in range(1, len(word)):
            yield word[0:last_char_index]
            
    def word_can_be_built_from_other_words(self, word: str) -> bool:
        """Проверка построения слова в соответствии с заданием"""
        return all([prefix in self.words_set for prefix in self.word_prefixes(word)])
            
    def longestWord(self, words: List[str]) -> str:
        """Поиск наиболее длинного слова, которое можно построить из имеющихся слова, прибавляя по одному символу"""
        self.words_set = set(words)
        
        # просматриваем слова с максимальной длиной, в лексикографическом порядке
        for word in sorted(words, key=lambda w: (-len(w), w)):
            if self.word_can_be_built_from_other_words(word):
                return word