MediumNo. 1858LeetCode Premium
Longest Word With All Prefixes — LeetCode 1858 Python Solution
- Pattern
- Trie
- Topics
- Depth-First Search, Trie, Array, String
- Reading time
- 6 min
- Source
- leetcode.com
The 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"].
Example
- 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.
Python solution
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 ansComplexity
- Time
- O(Σ_w ∈ words |w|)
- Space · auxiliary
- O(Σ_w ∈ words |w|)
Pattern: Trie
Store a set of words by their shared prefixes so lookups cost the length of the word. LeetCode 1858. Longest Word With All Prefixes is filed here because LeetCode tags it Trie, which is the vocabulary this hub collects.
The trie guide has the Python template for the pattern and the 49 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 1233 | Remove Sub-Folders from the Filesystem | Medium |
| 0211 | Design Add and Search Words Data Structure | Medium |
| 0130 | Surrounded Regions | Medium |
| 0200 | Number of Islands | Medium |
| 0297 | Serialize and Deserialize Binary Tree | Hard |
| 0386 | Lexicographical Numbers | Medium |
Frequently asked questions
- How hard is LeetCode 1858. Longest Word With All Prefixes?
LeetCode 1858. Longest Word With All Prefixes is rated Medium on LeetCode.
- What is the time complexity of LeetCode 1858. Longest Word With All Prefixes?
The Python solution on this page runs in O(Σ_w ∈ words |w|).
- What is the space complexity of LeetCode 1858. Longest Word With All Prefixes?
The Python solution on this page uses O(Σ_w ∈ words |w|) auxiliary space.
- What topics does LeetCode 1858. Longest Word With All Prefixes cover?
LeetCode 1858. Longest Word With All Prefixes is tagged Depth-First Search, Trie, Array and String on LeetCode.
- Is LeetCode 1858. Longest Word With All Prefixes a premium problem?
Yes. LeetCode 1858. Longest Word With All Prefixes is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.