Longest Word in Dictionary

Problem

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.

Example 1:

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".

Example 2:

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".

Constraints:

1 <= words.length <= 1000
1 <= words[i].length <= 30
words[i] consists of lowercase English letters.

Solution

/**
 * @param {string[]} words
 * @return {string}
 */
var longestWord = function(words) {
    const set = new Set([""]);
    let res = "";
    words.sort((a, b) => a.length - b.length);

    for (const s of words) {
        if (set.has(s.substring(0, s.length - 1))) {
            set.add(s);
            // if (s has greater length) or (equal length and smaller lexicographically)
            if (s.length > res.length || s.length === res.length && s < res) {
                res = s;
            }
        }
    }
    return res;
};

We first sort words by length. This way, it ensures all possible words s1 that is a proper prefix of s2 (in words) comes before s2. Thus, since a word s in words is only valid if s[0:s.length], ..., s[0:1] all also exist in words, starting from the shortest possible prefix s[0:1], we can build up all valid s and store them in set (ie. if s[0:s.length] is in set, then s is valid).

Note that another possible solution is to use a trie and perform DFS/BFS.

Problem​

Solution​

Problem

Solution