Longest Word in Dictionary

Problem Summary

• Given a list of unsorted words in an array
• Find the longest word that can be built only using one character at a time

Key Observations

• Sort since that would make everything easy
• One word at a time is important distinction
• We should add character in our Prefix Tree (Trie) only if it is the last character and the new character that we don't have in our Trie already

Approach Taken

• Build a prefix tree (Trie), every time you encounter a character that is the last character and new then create a node for it
• Also, check whether it is the longest we have seen so far and store
• Return the longest we saw otherwise an empty string

Why This Works

• We only build add nodes to our tree when we see new characters one at a time

Main Concepts Used

• Trie

Time & Space Complexity

• Time: $O(nlogn\ast L)$ → Reason: Sorting is dominant since that depends on number of words $n$ and average length of the word $L$
• Space: $O(n\ast L)$ → Reason: Worst case, we store all characters from words

Code

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


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

    def longestWord(self, words: List[str]) -> str:
        words.sort()  # ['a', 'ap', 'app', 'appl', 'apple', 'apply', 'b', 'ban', 'banana']
        lengthOflongestWord = 0
        longestWord = ""
        

        # build a prefix tree
        # TrieNode doenst exist we create and check current length with max length, and save word

        # {} 
        #  \ 
        #   a: {}  b
        #    \
        #     p: {}
        #.     \ 
        #.      p: {}
        #        \
        #         l
        #          \
        #           e

        for word in words:
            cur = self.root
            for i, c in enumerate(word): # 1, p
                if c not in cur.children and i != len(word) - 1:
                    break
                if c not in cur.children:
                    cur.children[c] = TrieNode()
                    currentLevel = i + 1
                    if currentLevel > lengthOflongestWord:
                        lengthOflongestWord = currentLevel
                        longestWord = word[:currentLevel]
                    break
                cur = cur.children[c]

        return longestWord

Common Mistakes / Things I Got Stuck On