Formatted question description: https://leetcode.ca/all/1858.html

1858. Longest Word With All Prefixes

Medium

Description

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 the lexicographically smallest one, and if no string exists, return "".

Example 1:

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:

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:

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

Solution

Use a trie to store all the words. Then do depth first search on the trie. Search the nodes from left to right to make sure that the leftmost nodes (with lexicographically smallest letters) are visited first. For the words that all nodes are ends of words, update the longest word. Finally, return the longest word.

• class Solution {
String longestWord = "";

public String longestWord(String[] words) {
TrieNode root = new TrieNode();
for (String word : words) {
TrieNode node = root;
int length = word.length();
for (int i = 0; i < length; i++) {
char letter = word.charAt(i);
int index = letter - 'a';
if (node.children[index] == null)
node.children[index] = new TrieNode();
node = node.children[index];
}
node.wordEnd = true;
}
depthFirstSearch(root, new StringBuffer());
return longestWord;
}

public void depthFirstSearch(TrieNode node, StringBuffer sb) {
if (node.wordEnd && sb.length() > longestWord.length())
longestWord = sb.toString();
for (int i = 0; i < 26; i++) {
TrieNode child = node.children[i];
if (child != null && child.wordEnd) {
sb.append((char) ('a' + i));
depthFirstSearch(child, sb);
sb.deleteCharAt(sb.length() - 1);
}
}
}
}

class TrieNode {
boolean wordEnd;
TrieNode[] children;

public TrieNode() {
wordEnd = false;
children = new TrieNode[26];
}
}

############

class Trie {
Trie[] children = new Trie[26];
boolean isEnd;

void insert(String w) {
Trie node = this;
for (char c : w.toCharArray()) {
c -= 'a';
if (node.children[c] == null) {
node.children[c] = new Trie();
}
node = node.children[c];
}
node.isEnd = true;
}

boolean search(String w) {
Trie node = this;
for (char c : w.toCharArray()) {
c -= 'a';
node = node.children[c];
if (!node.isEnd) {
return false;
}
}
return true;
}
}

class Solution {
public String longestWord(String[] words) {
Trie trie = new Trie();
for (String w : words) {
trie.insert(w);
}
String ans = "";
for (String w : words) {
if (!"".equals(ans)
&& (ans.length() > w.length()
|| (ans.length() == w.length() && ans.compareTo(w) < 0))) {
continue;
}
if (trie.search(w)) {
ans = w;
}
}
return ans;
}
}

• // OJ: https://leetcode.com/problems/longest-word-with-all-prefixes/
// Time: O(NW)
// Space: O(NW)
struct TrieNode {
TrieNode *next[26] = {};
bool word = false;
};
class Solution {
void addWord(TrieNode *node, string &s) {
for (char c : s) {
if (!node->next[c - 'a']) node->next[c - 'a'] = new TrieNode();
node = node->next[c - 'a'];
}
node->word = true;
}
string ans, path;
void dfs(TrieNode *node) {
for (int i = 0; i < 26; ++i) {
if (!node->next[i] || !node->next[i]->word) continue;
path += 'a' + i;
if (path.size() > ans.size()) ans = path;
dfs(node->next[i]);
path.pop_back();
}
}
public:
string longestWord(vector<string>& A) {
TrieNode root;
for (auto &s : A) addWord(&root, s);
dfs(&root);
return ans;
}
};

• class Trie:
def __init__(self):
self.children = [None] * 26
self.is_end = False

def insert(self, w):
node = self
for c in w:
idx = ord(c) - ord("a")
if node.children[idx] is None:
node.children[idx] = Trie()
node = node.children[idx]
node.is_end = True

def search(self, w):
node = self
for c in w:
idx = ord(c) - ord("a")
node = node.children[idx]
if not node.is_end:
return False
return True

class Solution:
def longestWord(self, words: List[str]) -> str:
trie = Trie()
for w in words:
trie.insert(w)
ans = ""
for w in words:
if ans and (len(ans) > len(w) or (len(ans) == len(w) and ans < w)):
continue
if trie.search(w):
ans = w
return ans


• type Trie struct {
children [26]*Trie
isEnd    bool
}

func newTrie() *Trie {
return &Trie{}
}
func (this *Trie) insert(word string) {
node := this
for _, c := range word {
c -= 'a'
if node.children[c] == nil {
node.children[c] = newTrie()
}
node = node.children[c]
}
node.isEnd = true
}
func (this *Trie) search(word string) bool {
node := this
for _, c := range word {
c -= 'a'
node = node.children[c]
if !node.isEnd {
return false
}
}
return true
}

func longestWord(words []string) string {
trie := newTrie()
for _, w := range words {
trie.insert(w)
}
ans := ""
for _, w := range words {
if ans != "" && (len(ans) > len(w) || (len(ans) == len(w) && ans < w)) {
continue
}
if trie.search(w) {
ans = w
}
}
return ans
}