Implement Prefix Tree (Trie)

Problem Statement

Create a prefix tree data structure with three main operations: addWord, findWord, and hasPrefix.

The addWord method inserts a word into the prefix tree. The findWord method returns whether a given word exists in the tree. The hasPrefix method checks if there is any word in the structure that starts with the given prefix.

Examples

PrefixTree tree = new PrefixTree();

tree.addWord("banana");
tree.findWord("banana");   // returns true
tree.findWord("ban");      // returns false
tree.hasPrefix("ban");     // returns true
tree.addWord("ban");
tree.findWord("ban");      // returns true
    

Constraints

• All input words and prefixes contain only lowercase English letters (a-z).
• Words and prefixes are guaranteed to be non-empty.
• The total number of calls to the methods will not exceed 3000.