LeetCode 1858. Longest Word With All Prefixes Solution in Java, C++, Python & More | Explanation + Code

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 <= 105
• 1 <= words[i].length <= 105
• 1 <= sum(words[i].length) <= 105
• words[i] consists only of lowercase English letters.

Solutions

Solution 1: Trie

We define a Trie where each node has two attributes: a child node array children of length 26, and a flag isEnd indicating whether the node marks the end of a word.

We iterate over words, and for each word w, we traverse from the root node. If the child node array of the current node does not contain the first character of w, we create a new node, then continue traversing the next character of w. After traversing all characters of w, we set the isEnd flag of the current node to \texttt{true}.

Next, we iterate over words again, and for each word w, we traverse from the root node. If the isEnd field of a node in the child node array is \texttt{false}, it means some prefix of w is not in words, and we return \texttt{false}. Otherwise, we continue traversing the next character of w, and after traversing all characters, we return \texttt{true}.

The time complexity is O(∑_{w ∈ words} |w|), and the space complexity is O(∑_{w ∈ words} |w|), where |w| is the length of word w.

PythonJavaC++GoTypeScriptRustJavaScriptC#

class Trie: __slots__ = ["children", "is_end"] def __init__(self): self.children: List[Trie | None] = [None] * 26 self.is_end: bool = False def insert(self, w: str) -> None: node = self for c in w: idx = ord(c) - ord("a") if not node.children[idx]: node.children[idx] = Trie() node = node.children[idx] node.is_end = True def search(self, w: str) -> bool: 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 (len(w) > len(ans) or len(w) == len(ans) and w < ans) and trie.search(w): ans = w return ans(code-box)

class Trie { private Trie[] children = new Trie[26]; private boolean isEnd; public Trie() { } public void insert(String w) { Trie node = this; for (char c : w.toCharArray()) { int idx = c - 'a'; if (node.children[idx] == null) { node.children[idx] = new Trie(); } node = node.children[idx]; } node.isEnd = true; } public boolean search(String w) { Trie node = this; for (char c : w.toCharArray()) { int idx = c - 'a'; node = node.children[idx]; 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 ((w.length() > ans.length() || (w.length() == ans.length() && w.compareTo(ans) < 0)) && trie.search(w)) { ans = w; } } return ans; } }(code-box)

class Trie { private: Trie* children[26]; bool isEnd = false; public: Trie() { fill(begin(children), end(children), nullptr); } void insert(const string& w) { Trie* node = this; for (char c : w) { int idx = c - 'a'; if (!node->children[idx]) { node->children[idx] = new Trie(); } node = node->children[idx]; } node->isEnd = true; } bool search(const string& w) { Trie* node = this; for (char c : w) { int idx = c - 'a'; node = node->children[idx]; if (!node->isEnd) { return false; } } return true; } }; class Solution { public: string longestWord(vector<string>& words) { Trie trie; for (const string& w : words) { trie.insert(w); } string ans = ""; for (const string& w : words) { if ((w.size() > ans.size() || (w.size() == ans.size() && w < ans)) && trie.search(w)) { ans = w; } } return ans; } };(code-box)

type Trie struct { children [26]*Trie isEnd bool } func newTrie() *Trie { return &Trie{} } func (t *Trie) insert(w string) { node := t for _, c := range w { idx := c - 'a' if node.children[idx] == nil { node.children[idx] = newTrie() } node = node.children[idx] } node.isEnd = true } func (t *Trie) search(w string) bool { node := t for _, c := range w { idx := c - 'a' node = node.children[idx] 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 (len(w) > len(ans) || (len(w) == len(ans) && w < ans)) && trie.search(w) { ans = w } } return ans }(code-box)

class Trie { private children: (Trie | null)[] = Array(26).fill(null); private isEnd: boolean = false; insert(w: string): void { let node: Trie = this; for (const c of w) { const idx: number = c.charCodeAt(0) - 'a'.charCodeAt(0); if (!node.children[idx]) { node.children[idx] = new Trie(); } node = node.children[idx] as Trie; } node.isEnd = true; } search(w: string): boolean { let node: Trie = this; for (const c of w) { const idx: number = c.charCodeAt(0) - 'a'.charCodeAt(0); node = node.children[idx] as Trie; if (!node.isEnd) { return false; } } return true; } } function longestWord(words: string[]): string { const trie: Trie = new Trie(); for (const w of words) { trie.insert(w); } let ans: string = ''; for (const w of words) { if ((w.length > ans.length || (w.length === ans.length && w < ans)) && trie.search(w)) { ans = w; } } return ans; }(code-box)

struct Trie { children: [Option<Box<Trie>>; 26], is_end: bool, } impl Trie { fn new() -> Self { Trie { children: Default::default(), is_end: false, } } fn insert(&mut self, w: &str) { let mut node = self; for c in w.chars() { let idx = (c as usize) - ('a' as usize); node = node.children[idx].get_or_insert_with(|| Box::new(Trie::new())); } node.is_end = true; } fn search(&self, w: &str) -> bool { let mut node = self; for c in w.chars() { let idx = (c as usize) - ('a' as usize); if let Some(next_node) = &node.children[idx] { node = next_node.as_ref(); if !node.is_end { return false; } } } true } } impl Solution { pub fn longest_word(words: Vec<String>) -> String { let mut trie = Trie::new(); for w in &words { trie.insert(w); } let mut ans = String::new(); for w in &words { if (w.len() > ans.len() || (w.len() == ans.len() && w < &ans)) && trie.search(w) { ans = w.clone(); } } ans } }(code-box)

class Trie { constructor() { this.children = new Array(26).fill(null); this.isEnd = false; } insert(w) { let node = this; for (const c of w) { const idx = c.charCodeAt(0) - 'a'.charCodeAt(0); if (!node.children[idx]) { node.children[idx] = new Trie(); } node = node.children[idx]; } node.isEnd = true; } search(w) { let node = this; for (const c of w) { const idx = c.charCodeAt(0) - 'a'.charCodeAt(0); node = node.children[idx]; if (!node || !node.isEnd) { return false; } } return true; } } /** * @param {string[]} words * @return {string} */ var longestWord = function (words) { const trie = new Trie(); for (const w of words) { trie.insert(w); } let ans = ''; for (const w of words) { if ((w.length > ans.length || (w.length === ans.length && w < ans)) && trie.search(w)) { ans = w; } } return ans; };(code-box)

public class Trie { private Trie[] children = new Trie[26]; private bool isEnd; public Trie() { } public void Insert(string w) { Trie node = this; foreach (char c in w.ToCharArray()) { int idx = c - 'a'; if (node.children[idx] == null) { node.children[idx] = new Trie(); } node = node.children[idx]; } node.isEnd = true; } public bool Search(string w) { Trie node = this; foreach (char c in w.ToCharArray()) { int idx = c - 'a'; node = node.children[idx]; if (!node.isEnd) { return false; } } return true; } } public class Solution { public string LongestWord(string[] words) { Trie trie = new Trie(); foreach (string w in words) { trie.Insert(w); } string ans = ""; foreach (string w in words) { if ((w.Length > ans.Length || (w.Length == ans.Length && string.Compare(w, ans) < 0)) && trie.Search(w)) { ans = w; } } return ans; } }(code-box)