Problem

A trie (pronounced as “try”) or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.

Implement the Trie class:

  • Trie() Initializes the trie object.
  • void insert(String word) Inserts the string word into the trie.
  • boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.
  • boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

Input:
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output:
[null, null, true, false, true, null, true]


Explanation:
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // return True
trie.search("app");     // return False
trie.startsWith("app"); // return True
trie.insert("app");
trie.search("app");     // return True

Solution

Method 1 - Using Map

Insert

Here is how we can insert in the trie:

  • Start at the root.
  • Search for the word’s first character among the root’s children.
    • For instance, with “AGRA” being the initial insertion, create a ‘A’ child for the root, followed by its descendants ‘G’, ‘R’, and ‘A’.
  • Proceed to the corresponding child node in the Trie and the next letter in the word if such a node is present.
    • For example, when inserting “AYODHYA” after ‘AGRA’, start at the root and locate the existing ‘A’ node. Moving to the ‘A’ node, search for ‘Y’ among its children. Absence of ‘Y’ implies it needs to be created as a new child of ‘A’.
  • On encountering a null child and additional unsaved characters in the word, sequentially append them as children. Thus ‘Y’ would be linked under ‘A’, ‘O’ under ‘Y’, and so forth.
  • At the end of word, set isEnd to true.

Code

1
2
3
4
5

class TrieNode {
    private boolean isWord;
    private String prefix;
    private Map<Character, TrieNode> children;
}
 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

class Trie {
	static class TrieNode {
		private boolean isEnd;
		private Map<Character, TrieNode> children = new HashMap<>();
	}

	public TrieNode root;

	/** Initialize your data structure here. */

	public Trie() {
		this.root = new TrieNode();
	}

	/** Inserts a word into the trie. */

	public void insert(String word) {
		TrieNode curr = this.root;

		for (char c: word.toCharArray()) {
			curr.children.putIfAbsent(c, new TrieNode());
			curr = curr.children.get(c);
		}

		curr.isEnd = true;
	}

	/** Returns if the word is in the trie. */

	public boolean search(String word) {
		return exists(word);
	}

	private boolean exists(String word) {
		TrieNode curr = root;

		for (char c: word.toCharArray()) {
			if (!curr.children.containsKey(c)) {
				return false;
			}

			curr = curr.children.get(c);
		}

		return curr.isEnd;
	}

	/** Returns if there is any word in the trie that starts with the given prefix. */

	public boolean startsWith(String prefix) {
		TrieNode curr = root;

		for (char c: prefix.toCharArray()) {
			if (!curr.children.containsKey(c)) {
				return false;
			}

			curr = curr.children.get(c);
		}

		return true;
	}
}

Method 2 - Using Array

As we have only 26 character set, we can use a array of those alphabets.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

class Trie {
	static class TrieNode {
		private boolean isEnd;
		private TrieNode[] children = new TrieNode[26];
	}

	public TrieNode root;

	/** Initialize your data structure here. */

	public Trie() {
		this.root = new TrieNode();
	}

	/** Inserts a word into the trie. */

	public void insert(String word) {
		TrieNode curr = this.root;

		for (char c: word.toCharArray()) {
			int idx = c - 'a';
			if (curr.children[idx] == null) {
				curr.children[idx] = new TrieNode();
			}
			curr = curr.children[idx];
		}
		
		curr.isEnd = true;
	}

	/** Returns if the word is in the trie. */

	public boolean search(String word) {
		return exists(word);
	}

	private boolean exists(String word) {
		TrieNode curr = root;
		
		for (char c: word.toCharArray()) {
			int idx = c - 'a';
			curr = curr.children[idx];
			if (curr == null) {
				return false;
			}
			
		}

		return curr.isEnd;
	}

	/** Returns if there is any word in the trie that starts with the given prefix. */

	public boolean startsWith(String prefix) {
		TrieNode curr = root;

		for (char c: prefix.toCharArray()) {
			int idx = c - 'a';
			curr = curr.children[idx];
			if (curr == null) {
				return false;
			}
		}

		return true;
	}
}