This approach involves creating a basic Trie data structure using a tree of nodes. Each node represents a character in a word. Starting from a root node, each character of the word is inserted sequentially, with branches representing the progression to subsequent characters. This forms a chain of nodes (linked in a tree-like manner) from the root to the nodes representing complete words. For searching, we traverse these nodes based on the characters of the input word or prefix to check for existence.
Time Complexity: Insert, search, and startsWith operations are O(m), where m is the length of the word/prefix.
Space Complexity: O(26 * n * m) in the worst case, where n is the number of inserted words and m is the average length of the words. Each insertion can potentially add m nodes with 26 possible children each.
1class TrieNode {
2 public TrieNode[] children;
3 public boolean isEndOfWord;
4
5 public TrieNode() {
6 children = new TrieNode[26];
7 isEndOfWord = false;
8 }
9}
10
11class Trie {
12 private TrieNode root;
13
14 public Trie() {
15 root = new TrieNode();
16 }
17
18 public void insert(String word) {
19 TrieNode node = root;
20 for (char ch : word.toCharArray()) {
21 int index = ch - 'a';
22 if (node.children[index] == null) {
23 node.children[index] = new TrieNode();
24 }
25 node = node.children[index];
26 }
27 node.isEndOfWord = true;
28 }
29
30 public boolean search(String word) {
31 TrieNode node = root;
32 for (char ch : word.toCharArray()) {
33 int index = ch - 'a';
34 if (node.children[index] == null) {
35 return false;
36 }
37 node = node.children[index];
38 }
39 return node.isEndOfWord;
40 }
41
42 public boolean startsWith(String prefix) {
43 TrieNode node = root;
44 for (char ch : prefix.toCharArray()) {
45 int index = ch - 'a';
46 if (node.children[index] == null) {
47 return false;
48 }
49 node = node.children[index];
50 }
51 return true;
52 }
53}In Java, we define a TrieNode class with an array to hold pointers to child nodes, along with a boolean flag to determine if the node marks the end of a word. The Trie class utilizes a root node which is initialized in the constructor. The insertion method iterates over characters converting them into indices. The search method confirms both the presence of each character in the string and that the node marking the final character signifies the end of a word. The startsWith method similarly checks for the presence of each character in the prefix, validating their sequence up until the prefix ends.
This approach relies on maps (or hashmaps) for storing children nodes dynamically. The advantage of using maps over arrays in this context arises from reduced space consumption when handling sparse trees since only existing characters are stored. Nodes manage their children using hash references, leading to more flexible branching.
Time Complexity: O(m) per operation where m is the word/prefix length.
Space Complexity: O(n * m), where n estimates the word count and m accounts for varying lengths since nodes only maintain necessary mappings.
1class TrieNode {
2 constructor() {
3 this.children = new Map();
4 this.isEndOfWord = false;
5 }
6}
7
8class Trie {
9 constructor() {
10 this.root = new TrieNode();
11 }
12
13 insert(word) {
14 let node = this.root;
15 for (let char of word) {
16 if (!node.children.has(char)) {
17 node.children.set(char, new TrieNode());
18 }
19 node = node.children.get(char);
20 }
21 node.isEndOfWord = true;
22 }
23
24 search(word) {
25 let node = this.root;
26 for (let char of word) {
27 if (!node.children.has(char)) {
28 return false;
29 }
30 node = node.children.get(char);
31 }
32 return node.isEndOfWord;
33 }
34
35 startsWith(prefix) {
36 let node = this.root;
37 for (let char of prefix) {
38 if (!node.children.has(char)) {
39 return false;
40 }
41 node = node.children.get(char);
42 }
43 return true;
44 }
45}The JavaScript version utilizes Map for storing node child references. Map is advantageous with its guaranteed key storability and inherent ordering. The insert method tracks through characters, setting or accessing nodes on the fly with hashmap properties. Searching evaluates characters' existence in path while confirming final node's end-markers during search. Prefix check seeks each character similarly ensuring entire path viability.