Problem of The Day: Longest Word With All Prefixes

Problem Statement

Intuition

The problem asks to find the longest word that can be built one character at a time by other words in the list. My initial thought is to use a trie data structure, which is well-suited for prefix-based problems like this.

Approach

1. Build the Trie: Insert all words into the trie. Each node represents a character of a word, and we mark the end of a word with a special character, say ##.
2. Validate Words: For each word, check if all prefixes of this word exist in the trie. If they do, consider this word as a potential answer.
3. Select the Longest Word: Track the longest word that satisfies the prefix condition. If there are multiple words of the same length, select the lexicographically smallest one.

Complexity

• Time complexity: \(O(n \cdot m)\), where \(n\) is the number of words and \(m\) is the maximum length of a word. We build the trie and then search for the valid word.

• Space complexity: \(O(n \cdot m)\), since the trie stores all characters of all words.

Code

class Solution:
    def longestWord(self, words: List[str]) -> str:
        res = ""
        trie = {}
        for word in words:
            curr = trie
            for c in word:
                if c not in curr:
                    curr[c] = {}
                curr = curr[c]
            curr['#'] = True

        for word in words:
            curr = trie
            valid = True
            for c in word:
                if c in curr:
                    curr = curr[c]
                    if '#' not in curr:
                        valid = False
                        break
            if valid:
                if len(res) < len(word):
                    res = word
                elif len(res) == len(word):
                    res = res if res < word else word

        return res

Editorial

Approach 1: Hash Set

class Solution:
    def longestWord(self, words: List[str]) -> str:
        # Sort the words lexicographically
        words.sort()

        # Set to store valid words
        valid_words = set()
        longest_valid_word = ""

        # Iterate through each word
        for current_word in words:
            # Check if the word is of length 1 or if its prefix exists in the set
            if len(current_word) == 1 or current_word[:-1] in valid_words:
                # Add the current word to the set of valid words
                valid_words.add(current_word)

                # Update the longest valid word if necessary
                if len(current_word) > len(longest_valid_word):
                    longest_valid_word = current_word

        # Return the longest valid word found
        return longest_valid_word

• time: O(l*n*logn) where n is length of word, l is the length of the longest word
• space: O(n*l+S)

Approach 2: Trie

class Solution:
    def longestWord(self, words: List[str]) -> str:
        trie = Trie()
        longest_valid_word = ""

        # Insert all words into the trie
        for word in words:
            trie._insert(word)

        # Check each word and update the longest valid word
        for word in words:
            if trie._has_all_prefixes(word):
                if len(word) > len(longest_valid_word) or (
                    len(word) == len(longest_valid_word)
                    and word < longest_valid_word
                ):
                    longest_valid_word = word

        return longest_valid_word


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

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

    # Insert a word into the trie
    def _insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = self.TrieNode()
            node = node.children[char]
        node.is_end_of_word = True

    # Check if all prefixes of the word exist in the trie
    def _has_all_prefixes(self, word):
        node = self.root
        for char in word:
            if (
                char not in node.children
                or not node.children[char].is_end_of_word
            ):
                return False
            node = node.children[char]
        return True