Implementing a Patricia Trie in JavaScript

This challenge asks you to implement a Patricia Trie (also known as a Radix Trie or Compact Prefix Tree) in JavaScript. Patricia Tries are a space-efficient data structure for storing strings, particularly useful for applications like auto-completion, spell checking, and IP routing where lookups need to be fast and memory usage is a concern. Your implementation should support insertion and searching of strings.

Problem Description

You need to create a PatriciaTrie class in JavaScript. This trie should efficiently store a collection of strings. Unlike a standard trie, a Patricia Trie compresses nodes that have only one child. This means that edges in the trie can represent sequences of characters rather than single characters.

Your implementation should include the following core functionalities:

• insert(word): Adds a given word (string) to the trie.
• search(word): Returns true if the word exists in the trie, and false otherwise.
• startsWith(prefix): Returns true if there is any word in the trie that starts with the given prefix, and false otherwise.

Key Requirements:

• Node Structure: You will need to define a node structure for your trie. Each node should store:
  • A map (e.g., JavaScript Map or object) of outgoing edges. The keys of this map will be the starting characters of the edge labels, and the values will be child nodes.
  • A label representing the string segment associated with the edge leading to this node from its parent.
  • A boolean flag (isEndOfWord) to indicate if the path leading to this node represents a complete word stored in the trie.
• Insertion Logic: When inserting a word, you need to handle cases where:
  • The word is a prefix of an existing word.
  • An existing word is a prefix of the new word.
  • The new word shares a common prefix with existing words, requiring node splitting.
  • The new word is entirely new.
• Search Logic: When searching for a word, you must traverse the trie following the edge labels.
• Prefix Search Logic: Similar to search, but you stop traversing once you've matched the entire prefix.

Edge Cases to Consider:

• Inserting an empty string.
• Searching for an empty string.
• Inserting duplicate strings.
• Words with shared prefixes that require splitting existing nodes.
• Words that are prefixes of other words already in the trie.
• Words that have existing words as prefixes.

Examples

Example 1:

Input:
trie = new PatriciaTrie();
trie.insert("apple");
trie.insert("app");
trie.insert("apricot");
trie.insert("banana");

Output:
trie.search("apple"): true
trie.search("app"): true
trie.search("apricot"): true
trie.search("banana"): true
trie.search("appl"): false
trie.search("ban"): false
trie.search("orange"): false
trie.startsWith("app"): true
trie.startsWith("apr"): true
trie.startsWith("ban"): true
trie.startsWith("ora"): false
trie.startsWith("appl"): true

Explanation:

The insert operations build the trie. For instance, "apple" and "app" share a common prefix. When "app" is inserted, the node representing "app" would be marked as isEndOfWord. When "apple" is inserted, it would extend from the "app" node. "apricot" would cause a split at "ap" if it wasn't already there, creating a new node for "ple" and "ricot". "banana" would form a separate branch.

Example 2:

Input:
trie = new PatriciaTrie();
trie.insert("test");
trie.insert("testing");
trie.insert("tester");

Output:
trie.search("test"): true
trie.search("testing"): true
trie.search("tester"): true
trie.search("testi"): false
trie.startsWith("test"): true
trie.startsWith("testi"): true
trie.startsWith("testin"): true
trie.startsWith("tes"): true

Explanation:

Here, "test" is a prefix of "testing" and "tester". When "test" is inserted, its node is marked as isEndOfWord. "testing" and "tester" will extend from this node. The startsWith method correctly identifies prefixes even if they aren't complete words themselves.

Example 3: (Node Splitting Scenario)

Input:
trie = new PatriciaTrie();
trie.insert("application");
trie.insert("apply");

Output:
trie.search("application"): true
trie.search("apply"): true
trie.startsWith("appli"): true

Explanation:

Initially, let's say "application" is inserted. The trie might have a node representing "application". When "apply" is inserted, it shares the prefix "appli". The algorithm needs to split the edge "application" at "appli" into two: one leading to a node with label "cation" and another leading to a node with label "y". The node for "apply" would be marked isEndOfWord.

Constraints

• The input word for insert, search, and startsWith will be strings composed of lowercase English letters (a-z).
• The maximum length of any input string is 100 characters.
• The number of words inserted into the trie will not exceed 10,000.
• Your implementation should aim for an average time complexity of O(L) for insertion and search operations, where L is the length of the string.

Notes

• Consider using a Map in JavaScript for storing child nodes to handle character keys efficiently.
• The core of the challenge lies in correctly handling the node splitting and merging logic when inserting words that share prefixes with existing paths in the trie.
• Think about how to represent the string segments on the edges of the trie nodes.
• For startsWith, you don't need the isEndOfWord flag to be true at the end of the prefix match. As long as a path exists for the prefix, it should return true.