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.

Note that the word should be built from left to right with each additional character being added to the end of a previous word.

Examples

Example 1

1
2
3


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

1
2
3


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

Method 1 – Trie and BFS

Intuition

To find the longest word that can be built one character at a time by other words, we need to ensure that all prefixes of the word exist in the dictionary. Using a Trie allows us to efficiently check for prefix existence, and BFS helps us find the longest word with the smallest lexicographical order.

Approach

Insert all words into a Trie, marking the end of each word.
Use BFS starting from the root, only enqueueing nodes that mark the end of a word (i.e., valid prefixes).
Track the word formed at each node. Update the answer if a longer or lexicographically smaller word is found.
Return the longest valid word found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


class TrieNode {
public:
    TrieNode* children[26] = {};
    string word = "";
};
class Solution {
public:
    string longestWord(vector<string>& words) {
        TrieNode* root = new TrieNode();
        for (auto& w : words) {
            TrieNode* node = root;
            for (char c : w) {
                if (!node->children[c-'a']) node->children[c-'a'] = new TrieNode();
                node = node->children[c-'a'];
            }
            node->word = w;
        }
        string ans = "";
        queue<TrieNode*> q;
        q.push(root);
        while (!q.empty()) {
            TrieNode* node = q.front(); q.pop();
            if (node->word.size() > ans.size() || (node->word.size() == ans.size() && node->word < ans)) ans = node->word;
            for (int i = 0; i < 26; ++i) {
                if (node->children[i] && node->children[i]->word != "") q.push(node->children[i]);
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33


type TrieNode struct {
    children [26]*TrieNode
    word string
}
func longestWord(words []string) string {
    root := &TrieNode{}
    for _, w := range words {
        node := root
        for _, c := range w {
            idx := int(c - 'a')
            if node.children[idx] == nil {
                node.children[idx] = &TrieNode{}
            }
            node = node.children[idx]
        }
        node.word = w
    }
    ans := ""
    q := []*TrieNode{root}
    for len(q) > 0 {
        node := q[0]
        q = q[1:]
        if len(node.word) > len(ans) || (len(node.word) == len(ans) && node.word < ans) {
            ans = node.word
        }
        for i := 0; i < 26; i++ {
            if node.children[i] != nil && node.children[i].word != "" {
                q = append(q, node.children[i])
            }
        }
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


class TrieNode {
    TrieNode[] children = new TrieNode[26];
    String word = "";
}
class Solution {
    public String longestWord(String[] words) {
        TrieNode root = new TrieNode();
        for (String w : words) {
            TrieNode node = root;
            for (char c : w.toCharArray()) {
                if (node.children[c-'a'] == null) node.children[c-'a'] = new TrieNode();
                node = node.children[c-'a'];
            }
            node.word = w;
        }
        String ans = "";
        Queue<TrieNode> q = new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()) {
            TrieNode node = q.poll();
            if (node.word.length() > ans.length() || (node.word.length() == ans.length() && node.word.compareTo(ans) < 0)) ans = node.word;
            for (int i = 0; i < 26; i++) {
                if (node.children[i] != null && !node.children[i].word.isEmpty()) q.offer(node.children[i]);
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


class TrieNode {
    val children = Array<TrieNode?>(26) { null }
    var word = ""
}
class Solution {
    fun longestWord(words: Array<String>): String {
        val root = TrieNode()
        for (w in words) {
            var node = root
            for (c in w) {
                val idx = c - 'a'
                if (node.children[idx] == null) node.children[idx] = TrieNode()
                node = node.children[idx]!!
            }
            node.word = w
        }
        var ans = ""
        val q = ArrayDeque<TrieNode>()
        q.add(root)
        while (q.isNotEmpty()) {
            val node = q.removeFirst()
            if (node.word.length > ans.length || (node.word.length == ans.length && node.word < ans)) ans = node.word
            for (i in 0 until 26) {
                node.children[i]?.let { if (it.word.isNotEmpty()) q.add(it) }
            }
        }
        return ans
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


class TrieNode:
    def __init__(self):
        self.children = {}
        self.word = ""
class Solution:
    def longestWord(self, words: list[str]) -> str:
        root = TrieNode()
        for w in words:
            node = root
            for c in w:
                if c not in node.children:
                    node.children[c] = TrieNode()
                node = node.children[c]
            node.word = w
        ans = ""
        q = [root]
        while q:
            node = q.pop(0)
            if len(node.word) > len(ans) or (len(node.word) == len(ans) and node.word < ans):
                ans = node.word
            for child in node.children.values():
                if child.word:
                    q.append(child)
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39


use std::collections::VecDeque;
struct TrieNode {
    children: [Option<Box<TrieNode>>; 26],
    word: String,
}
impl TrieNode {
    fn new() -> Self {
        Self { children: Default::default(), word: String::new() }
    }
}
impl Solution {
    pub fn longest_word(words: Vec<String>) -> String {
        let mut root = TrieNode::new();
        for w in &words {
            let mut node = &mut root;
            for &b in w.as_bytes() {
                let idx = (b - b'a') as usize;
                node = node.children[idx].get_or_insert_with(|| Box::new(TrieNode::new()));
            }
            node.word = w.clone();
        }
        let mut ans = String::new();
        let mut q = VecDeque::new();
        q.push_back(&root);
        while let Some(node) = q.pop_front() {
            if node.word.len() > ans.len() || (node.word.len() == ans.len() && node.word < ans) {
                ans = node.word.clone();
            }
            for child in &node.children {
                if let Some(child) = child {
                    if !child.word.is_empty() {
                        q.push_back(child);
                    }
                }
            }
        }
        ans
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


class TrieNode {
    children: Map<string, TrieNode> = new Map();
    word: string = "";
}
class Solution {
    longestWord(words: string[]): string {
        const root = new TrieNode();
        for (const w of words) {
            let node = root;
            for (const c of w) {
                if (!node.children.has(c)) node.children.set(c, new TrieNode());
                node = node.children.get(c)!;
            }
            node.word = w;
        }
        let ans = "";
        const q: TrieNode[] = [root];
        while (q.length) {
            const node = q.shift()!;
            if (node.word.length > ans.length || (node.word.length === ans.length && node.word < ans)) ans = node.word;
            for (const child of node.children.values()) {
                if (child.word) q.push(child);
            }
        }
        return ans;
    }
}

Complexity

⏰ Time complexity: O(nk), where n is the number of words and k is the average word length, for building the Trie and BFS.
🧺 Space complexity: O(nk), for the Trie and queue.

Problem#

Examples#

Example 1#

Example 2#

Constraints#

Solution#

Method 1 – Trie and BFS#

Intuition#

Approach#

Code#

Complexity#