Trie is an ordered tree data structure which stores words in it so that users can search a word or a prefix quickly. Time complexity for adding a word to a Trie is $O(l)$, and for searching a word or a prefix is $O(l)$ too ($l$ is the length of the word or the prefix being added or searched). So it’s why we prefer Trie rather than Set and Hash Table in some situations, such as Dynamic Set, Associative Array and a predictive text or autocomplete Dictionary.

Definition

  • The Trie is a tree where each node represents a single word or a prefix.
  • The root represents an empty string (“”), the nodes that are direct children of the root represent prefixes of length $1$, the nodes that are $2$ edges of distance from the root represent prefixes of length $2$, the nodes that are $3$ edges of distance from the root represent prefixes of length $3$ and so on. In other words, a node that is $k$ edges of distance of the root has an associated prefix of length $k$.
  • Let $v$ and $w$ be two nodes of the Trie, and assume that $v$ is the parent of $w$, then $v$ must have an associated prefix of $w$.

The figure below shows a Trie with the words “TREE”, “TRIE”, “ALGO”, “ASSOC”, “ALL”, and “ALSO.”

TrieTrie

LeetCode Problem

211. Add and Search Word - Data structure design

Design a data structure that supports the following two operations:
void addWord(word)
bool search(word)
search(word) can search a literal word or a regular expression string containing only letters “a-z” or “.”. A “.” means it can represent any one letter.

For example:

addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true

Note:

You may assume that all words are consist of lowercase letters a-z.

Solution

Since this problem need us to find whether that word actually exists or not, so we shouldn’t treat that word as a prefix of another word. Implementing a variant Trie with a flag representing it’s an end of a word can resolve that problem discussed before.
This is the data structure called TrieNode:

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
class TrieNode {
private static final int SIZE = 26;
private TrieNode[] edges;
// flag to represent whether this is an end of a word or not.
private boolean isWord;

public TrieNode() {
edges = new TrieNode[SIZE];
isWord = false;
}

public void setWord() {
isWord = true;
}

public boolean isWord() {
return isWord;
}

public boolean has(char ch) {
return edges[indexOf(ch)] != null;
}

public TrieNode add(char ch) {
TrieNode node = new TrieNode();
edges[indexOf(ch)] = node;
return node;
}

public TrieNode next(char ch) {
return edges[indexOf(ch)];

}

public List<TrieNode> getEdges() {
List<TrieNode> list = new ArrayList<>(SIZE);

for (TrieNode node: edges) {
if (node != null) {
list.add(node);
}
}

return list;
}

private int indexOf(char ch) {
return ch - 'a';
}
}

So to solve this LeetCode problem, all we need now is to implement methods addWord(String word) and search(String word):

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
public class WordDictionary {
private TrieNode head = new TrieNode();

// Adds a word into the data structure.
public void addWord(String word) {
TrieNode current = head;
for (int i = 0; i < word.length(); i++) {
char ch = word.charAt(i);
if (current.has(ch)) {
current = current.next(ch);
} else {
current = current.add(ch);
}

}
current.setWord();
}

// Returns if the word is in the data structure. A word could
// contain the dot character '.' to represent any one letter.
public boolean search(String word) {
return search(head, word);
}

private boolean search(TrieNode node, String word) {
if (word.isEmpty()) {
return node.isWord();
}

char firstChar = word.charAt(0);
String subStr = word.substring(1);

if (firstChar == '.') {
boolean found = false;

for (TrieNode next: node.getEdges()) {
found |= search(next, subStr);
}

return found;
} else {
return node.has(firstChar) && search(node.next(firstChar), subStr);
}
}
}