Code Implementation

class Solution:
    def longestWord(self, words):
        words_set = set(words)
        words.sort()
        longest = ""
        for word in words:
            if all(word[:k] in words_set for k in range(1, len(word))):
                if len(word) > len(longest):
                    longest = word
        return longest
      

class Solution {
public:
    string longestWord(vector<string>& words) {
        unordered_set<string> wordsSet(words.begin(), words.end());
        sort(words.begin(), words.end());
        string longest = "";
        for (const string& word : words) {
            bool valid = true;
            for (int k = 1; k < word.size(); ++k) {
                if (!wordsSet.count(word.substr(0, k))) {
                    valid = false;
                    break;
                }
            }
            if (valid && word.size() > longest.size()) {
                longest = word;
            }
        }
        return longest;
    }
};
      

class Solution {
    public String longestWord(String[] words) {
        Set<String> wordsSet = new HashSet<>(Arrays.asList(words));
        Arrays.sort(words);
        String longest = "";
        for (String word : words) {
            boolean valid = true;
            for (int k = 1; k < word.length(); ++k) {
                if (!wordsSet.contains(word.substring(0, k))) {
                    valid = false;
                    break;
                }
            }
            if (valid && word.length() > longest.length()) {
                longest = word;
            }
        }
        return longest;
    }
}
      

var longestWord = function(words) {
    const wordsSet = new Set(words);
    words.sort();
    let longest = "";
    for (const word of words) {
        let valid = true;
        for (let k = 1; k < word.length; ++k) {
            if (!wordsSet.has(word.substring(0, k))) {
                valid = false;
                break;
            }
        }
        if (valid && word.length > longest.length) {
            longest = word;
        }
    }
    return longest;
};
      

Problem Description

You are given a list of strings words. Your task is to find the longest word in words that can be built one character at a time by other words in words. This means for every prefix of the word (excluding the full word itself), that prefix must also be present in the list.

If there are multiple possible answers, return the one that is lexicographically smallest. Assume all words are made up of lowercase English letters.

• Each prefix of the answer (except itself) must also be a word in words.
• If there are ties, return the lexicographically smallest word.

Thought Process

At first glance, you might think about checking every word and seeing if all its prefixes exist in the list. However, doing this naively for every word could be slow if the list is large.

A brute-force approach would be to, for each word, generate all its prefixes and check if each one is in the list. This would require checking up to O(N * L) prefixes (where N is the number of words and L is the average word length), and if each check is O(N) (using a list), that’s slow.

To optimize, we can use a set or hash map for fast lookups of whether a prefix exists. Sorting the list helps us pick the lexicographically smallest word in case of ties.

Solution Approach

• Step 1: Store all words in a set.
  • This allows for O(1) lookup to check if a prefix exists.
• Step 2: Sort the words lexicographically.
  • This ensures that if two words have the same length, the lexicographically smaller one comes first.
• Step 3: Iterate through each word.
  • For each word, check if every prefix (from length 1 up to length len(word)-1) exists in the set.
  • If all prefixes exist, and the word is longer than the current longest, update the answer.
• Step 4: Return the result.
  • After checking all words, return the longest valid word found.

We use a set for quick prefix existence checks, and sorting for tie-breaking. This approach ensures efficiency and correctness.

Example Walkthrough

Sample input: ["w","wo","wor","worl","world","banana","ban","bana","banan"]

1. All words are stored in a set for fast lookup.
2. Words are sorted: ["ban","banana","banan","bana","w","wo","worl","world","wor"] (actual order may vary by implementation, but the concept holds).
3. Iterate through each word:
   • "w": No prefixes to check (single letter), so it's valid.
   • "wo": Prefix "w" exists, valid. It's longer than "w", so update answer to "wo".
   • "wor": Prefixes "w", "wo" exist, valid. Longer than "wo", update answer to "wor".
   • "worl": Prefixes "w", "wo", "wor" exist, valid. Update answer to "worl".
   • "world": Prefixes "w", "wo", "wor", "worl" exist, valid. Update answer to "world".
   • Other words like "banana" fail because not all prefixes ("b", "ba", etc.) are present.
4. The final answer is "world".

Time and Space Complexity

• Brute-force approach:
  • For each word, check all prefixes using a list: O(N * L * N), which is slow for large N.
• Optimized approach:
  • Sorting: O(N \log N) for N words.
  • For each word, checking all prefixes: O(N * L) (since set lookups are O(1)).
  • Total: O(N \log N + N * L).
  • Space: O(N * L) for the set and storing words.

Summary

The problem asks for the longest word that can be built one character at a time using other words from the list, where every prefix must also be present. By leveraging a set for fast prefix lookups and sorting for tie-breaking, we can efficiently find the answer. The key insight is to check all prefixes for each word, and using a set ensures this is done quickly. This approach balances clarity and efficiency, making it suitable for both beginners and experienced programmers.