720. Longest Word in Dictionary, Solution with step by step explanation
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n\n    words.sort()\n\nWe sort the list of words in lexicographical order.
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n```\n    words.sort()\n```\nWe sort the list of words in lexicographical order. This ensures that when two words of equal length qualify as an answer, the word which appears first in lexicographical order will be considered first.\n\n```\n    word_set, ans = set([\'\']), \'\'\n```\nword_set: a set containing an empty string. This will be used to keep track of words we\'ve processed and can build upon. The reason we start with an empty string is so that words of length 1 can be directly added, since their prefix (an empty string) is present.\nans: an empty string that will store our current longest word that meets the criteria.\n\n```\n    for word in words:\n```\nWe iterate over the sorted list of words.\n\n```\n        if word[:-1] in word_set:\n```\nFor each word, we check if its prefix (i.e., the word without its last character) is present in word_set. This is the condition to see if the word can be built character by character from the words we\'ve seen so far.\n\n```\n            if len(word) > len(ans):\n                ans = word\n```\nIf the current word is longer than our current answer ans, we update ans to be the current word.\n\n```\n            word_set.add(word)\n```\n\nAfter checking the current word, we add it to word_set because it can be used as a prefix for future words.\n\n```\n    return ans\n```\nAfter processing all words, we return the answer ans.\n\n# Complexity\n- Time complexity:\nO(n log n)\n\n- Space complexity:\nO(n)\n\n# Code\n```\nclass Solution:\n  def longestWord(self, words: List[str]) -> str:\n    words.sort()\n\n    word_set, ans = set([\'\']), \'\'\n\n    for word in words:\n        if word[:-1] in word_set:\n            if len(word) > len(ans):\n                ans = word\n            word_set.add(word)\n    \n    return ans\n\n```
['Array', 'Hash Table', 'String', 'Trie', 'Sorting', 'Python', 'Python3']