Practice/TikTok/Leetcode 208. Implement Trie (Prefix Tree)

Leetcode 208. Implement Trie (Prefix Tree)

CodingMust

Problem

Design and implement a dictionary data structure that supports efficient word storage and retrieval operations. Your dictionary should handle three core operations:

1. Add a word: Store a new word in the dictionary
2. Find a word: Check if an exact word exists in the dictionary
3. Check prefix: Determine if any word in the dictionary starts with a given prefix

The dictionary needs to efficiently handle strings containing only lowercase English letters (a-z).

Requirements

1. Implement a Dictionary class with the following methods:

   • __init__() or constructor(): Initialize an empty dictionary
   • add(word): Add a word to the dictionary
   • find(word): Return true if the exact word exists in the dictionary, false otherwise
   • hasPrefix(prefix): Return true if at least one word in the dictionary starts with the given prefix, false otherwise

2. Each method should execute efficiently relative to the length of the input string

3. Handle multiple operations on the same dictionary instance

Constraints

• 1 ≤ number of operations ≤ 30,000
• 1 ≤ word.length, prefix.length ≤ 2,000
• word and prefix consist only of lowercase English letters
• At most 20,000 calls will be made to add
• At most 10,000 calls combined will be made to find and hasPrefix

Examples

Example 1:

` Operations: ["initialize", "add", "find", "find", "hasPrefix", "hasPrefix"] Arguments: [[], ["hello"], ["hello"], ["help"], ["hel"], ["hex"]] Output: [null, null, true, false, true, false] Explanation:

• Initialize empty dictionary
• Add "hello" to dictionary
• Find "hello" returns true (exists)
• Find "help" returns false (not added)
• Prefix "hel" returns true (found in "hello")
• Prefix "hex" returns false (no words start with "hex") `

Example 2:

` Operations: ["initialize", "add", "add", "add", "hasPrefix", "find"] Arguments: [[], ["test"], ["testing"], ["tester"], ["test"], ["test"]] Output: [null, null, null, null, true, true] Explanation:

• Initialize empty dictionary
• Add "test", "testing", and "tester"
• Prefix "test" exists (all three words start with it)
• Word "test" exists as exact match `

Example 3:

` Operations: ["initialize", "hasPrefix", "find", "add", "hasPrefix", "find"] Arguments: [[], ["word"], ["word"], ["word"], ["word"], ["word"]] Output: [null, false, false, null, true, true] Explanation:

• Empty dictionary has no words or prefixes
• After adding "word", both prefix and exact searches return true `