Tree of Characters: Build a Trie from a Word List and Support Prefix Search and Word Existence Queries

Question

## Problem

Build a Trie (prefix tree) that supports:
- `insert(word)` -- add a word.
- `search(word) -> bool` -- return True if the word exists.
- `starts_with(prefix) -> bool` -- return True if any word starts with the prefix.
- `words_with_prefix(prefix) -> list[str]` -- return all words sharing the prefix.

```python
class Trie:
    def insert(self, word: str) -> None: ...
    def search(self, word: str) -> bool: ...
    def starts_with(self, prefix: str) -> bool: ...
    def words_with_prefix(self, prefix: str) -> list[str]: ...
```

**Example:**
```
t = Trie()
t.insert("apple"); t.insert("app"); t.insert("apex")
t.search("app")           -> True
t.starts_with("ap")       -> True
t.words_with_prefix("ap") -> ["app", "apple", "apex"]
```

## Follow-ups
1. What is the space complexity of a Trie vs. a sorted list for dictionary lookup?
2. Add `delete(word)` without leaving orphan nodes. What is the tricky case?
3. Implement fuzzy search: return all words within edit distance 1 of a query string using the Trie.
4. The dictionary has 10 million words. What compression scheme (e.g., DAWG, Patricia trie) would you use?

Tree of Characters: Build a Trie from a Word List and Support Prefix Search and Word Existence Queries

Question Details

Full Details

Topics

More from Square/Block