Longest Word With All Prefixes — LeetCode 1858 Python Solution
MediumLeetCode PremiumDepth-First SearchTrieArrayString
- Problem
- #1858
- Pattern
- Trie
- 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
Python
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
| Measure | Complexity |
|---|---|
| Time | O(\sum_{w \in words} |w|) |
| Space | O(\sum_{w \in words} |w|) auxiliary |
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
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(\sum_{w \in words} |w|).
- What is the space complexity of LeetCode 1858. Longest Word With All Prefixes?
- The Python solution on this page uses O(\sum_{w \in 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.