Leetcode 720 Longest Word in Dictionary

Given an array of strings words representing an English Dictionary, return 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. If there is no answer, return the empty string.

Input: words = ["w","wo","wor","worl","world"]
Output: "world"
Explanation: The word "world" can be built one character at a time by "w", "wo", "wor", and "worl".

Input: words = ["a","banana","app","appl","ap","apply","apple"]
Output: "apple"
Explanation: Both "apply" and "apple" can be built from other words in the dictionary. However, "apple" is lexicographically smaller than "apply".

• Burada bize kelimelerden oluşan bir liste veriliyor.Her kelimeden bir harf alıp ekleyerek listedeki en uzun kelimeyi bulmamız isteniyor.
• Bunun için pythonda set kullanarak bir liste oluşturabiliriz.Set kullandığımız taktirde aynı kelimeden iki tane bu listeye giremeyecektir.
• Daha sonra sorted metodu ile kelimeleri sıralarız.
• Sıralanmış kelimeler içinde dolaşarak yeni kelimenin(word) son karakteri olmayan halini örneğin kelimemiz apple ise appl kelimesini kendi valid listemizde ararız.Eğer listemizde appl var ise apple kelimemizi listemize ekleriz.
• Bu sayede elimizde sıralı olarak ['', ‘a’, ‘ap’, ‘app’, ‘appl’, ‘apple’, ‘apply’] bir liste oluşur.
• Bu listeyi de uzunluğa göre sıralarsak max alırsak apple elde ederiz.
• sorted fonksiyonu t.c. nlogn dir.for döngüsüde n dir. n + nlogn = nlogn

    def longestWord(self, words):
        valid = set([''])
        for word in sorted(words):
            if word[:-1] in valid:
                valid.add(word)
        return max(sorted(valid), key=len)