Longest Word With All Prefixes

Problem

Given an array of strings words, find the longest string in words such that every prefix of it is also in words.

For example, let words = ["a", "app", "ap"]. The string "app" has prefixes "ap" and "a", all of which are in words.

Return _the string described above. If there is more than one string with the same length, return thelexicographically smallest one, and if no string exists, return _"".

Examples

Example 1:

1
2
3


Input: words = ["k","ki","kir","kira", "kiran"]
Output: "kiran"
Explanation: "kiran" has prefixes "kira", "kir", "ki", and "k", and all of them appear in words.

Example 2:

1
2
3
4


Input: words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]
Output: "apple"
Explanation: Both "apple" and "apply" have all their prefixes in words.
However, "apple" is lexicographically smaller, so we return that.

Example 3:

1
2


Input: words = ["abc", "bc", "ab", "qwe"]
Output: ""

Constraints:

1 <= words.length <= 10^5
1 <= words[i].length <= 10^5
1 <= sum(words[i].length) <= 10^5
words[i] consists only of lowercase English letters.

Solution

Method 1 – Trie and DFS

Intuition

To find the longest word where every prefix is also in the list, we use a Trie to store all words and then perform DFS, only continuing down paths where all prefixes are valid words. This ensures that the word we build has all its prefixes present.

Approach

Insert all words into a Trie, marking the end of each word.
Perform DFS from the root, only visiting nodes that mark the end of a word (valid prefix).
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
31
32
33


class TrieNode {
public:
    TrieNode* children[26] = {};
    bool isWord = false;
};
class Solution {
public:
    string ans = "";
    void dfs(TrieNode* node, string& path) {
        if (path.size() > ans.size() || (path.size() == ans.size() && path < ans)) ans = path;
        for (int i = 0; i < 26; ++i) {
            if (node->children[i] && node->children[i]->isWord) {
                path.push_back('a' + i);
                dfs(node->children[i], path);
                path.pop_back();
            }
        }
    }
    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->isWord = true;
        }
        string path = "";
        dfs(root, path);
        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


type TrieNode struct {
    children [26]*TrieNode
    isWord bool
}
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.isWord = true
    }
    var ans, path string
    var dfs func(*TrieNode, string)
    dfs = func(node *TrieNode, path string) {
        if len(path) > len(ans) || (len(path) == len(ans) && path < ans) {
            ans = path
        }
        for i := 0; i < 26; i++ {
            if node.children[i] != nil && node.children[i].isWord {
                dfs(node.children[i], path+string('a'+i))
            }
        }
    }
    dfs(root, "")
    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


class TrieNode {
    TrieNode[] children = new TrieNode[26];
    boolean isWord = false;
}
class Solution {
    String ans = "";
    void dfs(TrieNode node, StringBuilder path) {
        if (path.length() > ans.length() || (path.length() == ans.length() && path.toString().compareTo(ans) < 0)) ans = path.toString();
        for (int i = 0; i < 26; i++) {
            if (node.children[i] != null && node.children[i].isWord) {
                path.append((char)('a'+i));
                dfs(node.children[i], path);
                path.deleteCharAt(path.length()-1);
            }
        }
    }
    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.isWord = true;
        }
        dfs(root, new StringBuilder());
        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


class TrieNode {
    val children = Array<TrieNode?>(26) { null }
    var isWord = false
}
class Solution {
    var ans = ""
    fun dfs(node: TrieNode, path: StringBuilder) {
        if (path.length > ans.length || (path.length == ans.length && path.toString() < ans)) ans = path.toString()
        for (i in 0 until 26) {
            node.children[i]?.let {
                if (it.isWord) {
                    path.append('a'+i)
                    dfs(it, path)
                    path.deleteCharAt(path.length-1)
                }
            }
        }
    }
    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.isWord = true
        }
        dfs(root, StringBuilder())
        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


class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = False
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.is_word = True
        ans = ""
        def dfs(node, path):
            nonlocal ans
            if len(path) > len(ans) or (len(path) == len(ans) and path < ans):
                ans = path
            for c in sorted(node.children):
                child = node.children[c]
                if child.is_word:
                    dfs(child, path + c)
        dfs(root, "")
        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


use std::collections::BTreeMap;
struct TrieNode {
    children: BTreeMap<char, TrieNode>,
    is_word: bool,
}
impl TrieNode {
    fn new() -> Self {
        Self { children: BTreeMap::new(), is_word: false }
    }
}
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 c in w.chars() {
                node = node.children.entry(c).or_insert_with(TrieNode::new);
            }
            node.is_word = true;
        }
        let mut ans = String::new();
        fn dfs(node: &TrieNode, path: &mut String, ans: &mut String) {
            if path.len() > ans.len() || (path.len() == ans.len() && path < ans) {
                *ans = path.clone();
            }
            for (&c, child) in &node.children {
                if child.is_word {
                    path.push(c);
                    dfs(child, path, ans);
                    path.pop();
                }
            }
        }
        let mut path = String::new();
        dfs(&root, &mut path, &mut ans);
        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


class TrieNode {
    children: Map<string, TrieNode> = new Map();
    isWord: boolean = false;
}
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.isWord = true;
        }
        let ans = "";
        function dfs(node: TrieNode, path: string) {
            if (path.length > ans.length || (path.length === ans.length && path < ans)) ans = path;
            for (const [c, child] of Array.from(node.children.entries()).sort()) {
                if (child.isWord) dfs(child, path + c);
            }
        }
        dfs(root, "");
        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 DFS.
🧺 Space complexity: O(nk), for the Trie and recursion stack.

Problem#

Examples#

Solution#

Method 1 – Trie and DFS#

Intuition#

Approach#

Code#

Complexity#