Implement a Trie Data Structure

The Trie, also known as a prefix tree, is a specialized tree-like data structure that stores a dynamic set or associative array where the keys are usually strings. It's particularly efficient for operations involving prefixes, such as autocomplete suggestions or spell checking. Your task is to implement a Trie data structure from scratch.

Problem Description

You need to implement a Trie class that supports the following operations:

1. insert(word): Adds a word to the Trie.
2. search(word): Returns true if the word is present in the Trie, and false otherwise.
3. startsWith(prefix): Returns true if there is any word in the Trie that starts with the given prefix, and false otherwise.

A Trie node should typically contain:

• A way to store references to its children nodes. This can be an array (if the alphabet size is fixed and small, like 26 for lowercase English letters) or a map/dictionary.
• A flag (boolean) to indicate if the current node marks the end of a complete word.

Key Requirements:

• The Trie should be able to handle words consisting of lowercase English letters ('a' through 'z').
• Implement the insert, search, and startsWith methods as described.

Expected Behavior:

• insert: Successfully adds the word. If the word already exists, the Trie should remain unchanged.
• search: Returns true only if the entire word exists and is marked as a complete word in the Trie.
• startsWith: Returns true if any word or prefix in the Trie matches the given prefix.

Edge Cases:

• Inserting an empty string.
• Searching for an empty string.
• Searching for a prefix that is also a complete word.
• Words that are prefixes of other words (e.g., inserting "app" and then "apple").

Examples

Example 1:

Trie trie = new Trie();
trie.insert("apple");
boolean result1 = trie.search("apple");   // Output: true
boolean result2 = trie.search("app");     // Output: false
boolean result3 = trie.startsWith("app"); // Output: true
trie.insert("app");
boolean result4 = trie.search("app");     // Output: true

Explanation:

1. insert("apple"): Adds "apple" to the Trie.
2. search("apple"): Returns true because "apple" is a complete word in the Trie.
3. search("app"): Returns false because "app" was inserted as a prefix for "apple", but not as a complete word itself.
4. startsWith("app"): Returns true because there's at least one word ("apple") that starts with "app".
5. insert("app"): Adds "app" as a complete word to the Trie.
6. search("app"): Now returns true because "app" has been explicitly added as a complete word.

Example 2:

Trie trie = new Trie();
trie.insert("bad");
trie.insert("dad");
trie.insert("mad");
boolean result1 = trie.search("pad");    // Output: false
boolean result2 = trie.startsWith("ma"); // Output: true
trie.insert("pad");
boolean result3 = trie.search("pad");    // Output: true

Explanation:

1. insert calls add "bad", "dad", and "mad".
2. search("pad"): Returns false as "pad" is not in the Trie.
3. startsWith("ma"): Returns true because "mad" starts with "ma".
4. insert("pad"): Adds "pad" to the Trie.
5. search("pad"): Returns true because "pad" is now a complete word.

Example 3: Edge Cases

Trie trie = new Trie();
trie.insert(""); // Inserting an empty string
boolean result1 = trie.search("");      // Output: true
boolean result2 = trie.startsWith("");  // Output: true
trie.insert("a");
boolean result3 = trie.search("a");     // Output: true
boolean result4 = trie.startsWith("b"); // Output: false

Explanation:

1. Inserting an empty string marks the root node as a word ending.
2. search("") returns true.
3. startsWith("") returns true (as an empty prefix matches everything).
4. search("a") returns true after inserting "a".
5. startsWith("b") returns false as no word starts with "b".

Constraints

• The Trie will only contain words composed of lowercase English letters ('a'-'z').
• The maximum length of a word or prefix will not exceed 100 characters.
• The total number of words inserted into the Trie will not exceed 10,000.
• The total number of search/startsWith operations will not exceed 10,000.
• Your implementation should aim for an efficient time complexity, ideally O(L) for insert, search, and startsWith, where L is the length of the word/prefix.

Notes

• Consider how you will represent the Trie nodes and their children. A common approach is to use an array of size 26 for children, where each index corresponds to a letter of the alphabet, or a hash map/dictionary for more flexibility.
• Pay close attention to the difference between search (requiring a complete word) and startsWith (requiring any word to have the given prefix).
• When inserting a word, ensure that the final node for the word is marked as a word ending.
• When checking for a prefix, you only need to traverse the Trie up to the length of the prefix. If the traversal is successful, startsWith should return true.