Practice › Trie
Longest Word with All Prefixes
Medium · Trie · Asked at Google, Amazon, Pinterest
Find the longest word in the list such that every prefix of it is also in the list (for "apple": a, ap, app, appl must all be present). If several have the same length, print the lexicographically smallest. If no word qualifies, print None.
Input
First line: n. Second line: n lowercase words.
Output
The word, or None.
Constraints
- 1 ≤ n ≤ 10^5
- total length ≤ 10^5
Insert all words into a trie; then DFS only through nodes that end a word.
Example 1
Input
7 a banana app appl ap apply apple
Output
apple
Example 2
Input
3 ab abc bcd
Output
None
Hints
- Insert every word into a trie and mark the nodes where words end.
- A word qualifies exactly when every node on its path is marked as a word end. DFS only through marked nodes.
Approach
Build the trie. Starting from the root, DFS into a child only if that child ends a word — so every string reached has all its prefixes present. Visit children in alphabetical order and replace the best answer only when the current string is strictly longer; that way, among equal lengths the alphabetically first one (visited first) is kept. If no letter at depth 1 is a word, the answer is "None".
Complexity: O(total length) time · O(total length · 26) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
struct TrieNode {
int next[26];
bool end = false;
TrieNode() { memset(next, -1, sizeof next); }
};
vector<TrieNode> t(1);
string best, cur;
void dfs(int node) {
if (cur.size() > best.size()) best = cur;
for (int c = 0; c < 26; c++) {
int nx = t[node].next[c];
if (nx >= 0 && t[nx].end) {
cur.push_back(char('a' + c));
dfs(nx);
cur.pop_back();
}
}
}
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
string w;
cin >> w;
int node = 0;
for (char c : w) {
if (t[node].next[c - 'a'] < 0) {
t[node].next[c - 'a'] = t.size();
t.emplace_back();
}
node = t[node].next[c - 'a'];
}
t[node].end = true;
}
dfs(0);
cout << (best.empty() ? "None" : best) << "\n";
return 0;
}Python solution
import sys
sys.setrecursionlimit(300000)
data = sys.stdin.read().split()
root = {}
for w in data[1 : 1 + int(data[0])]:
node = root
for c in w:
node = node.setdefault(c, {})
node["$"] = True
best = ""
stack = [(root, "")]
while stack:
node, cur = stack.pop()
if len(cur) > len(best) or (len(cur) == len(best) and cur < best):
best = cur
for c, child in node.items():
if c != "$" and "$" in child:
stack.append((child, cur + c))
print(best or "None")Java solution
import java.util.*;
public class Main {
static class TrieNode {
TrieNode[] next = new TrieNode[26];
boolean end;
}
static String best = "";
static StringBuilder cur = new StringBuilder();
static void dfs(TrieNode node) {
if (cur.length() > best.length()) best = cur.toString();
for (int c = 0; c < 26; c++) {
TrieNode nx = node.next[c];
if (nx != null && nx.end) {
cur.append((char) ('a' + c));
dfs(nx);
cur.deleteCharAt(cur.length() - 1);
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
TrieNode root = new TrieNode();
for (int i = 0; i < n; i++) {
TrieNode node = root;
for (char c : sc.next().toCharArray()) {
if (node.next[c - 'a'] == null) node.next[c - 'a'] = new TrieNode();
node = node.next[c - 'a'];
}
node.end = true;
}
dfs(root);
System.out.println(best.isEmpty() ? "None" : best);
}
}Solve Longest Word with All Prefixes online · All practice problems