Trie Tree

Typically, a trie (reTRIEval, pronounce ‘try’, also known as prefix tree and radix tree) is used to store strings. Each Trie node represents a prefix string. The child nodes represent will be the origin string represented by the node itself plus the next character on the path.

Trie Tree

Trie Tree

All the descendants of a node have a common prefix of the string associated with that node. Trie widely used in applications like autocomplete, spell checker.

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
struct TrieNode {
unordered_map<char, TrieNode*> next;
bool isTerm = false;
};

class Trie {
public:
Trie() {
root = new TrieNode();
}

void insert(string word) {
auto p = root;
for (auto c : word) {
if (p->next.find(c) == p->next.end()) {
p->next[c] = new TrieNode();
}
p = p->next[c];
}
p->label = true;
}

bool search(string word) {
auto p = root;
for (auto c : word) {
if (p->next.find(c) == p->next.end()) {
return false;
}
p = p->next[c];
}
return p->label;
}

bool startsWith(string prefix) {
auto p = root;
for (auto c : prefix) {
if (p->next.find(c) == p->next.end()) {
return false;
}
p = p->next[c];
}
return true;
}
private:
TrieNode* root;
};

A more concise version

1
2
3
4
5
6
7
8
class TrieNode {
vector<TrieNode *> next;
string word; // word = "" if not leaf node

TrieNode () {
next = vector<TrieNode *>(26, nullptr);
}
}

Word Search II

Given a 2D board and a list of words from the dictionary, find all words in the board. Each word must be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

1
2
3
4
5
6
7
8
9
10
Input: 
words = ["oath","pea","eat","rain"] and board =
[
['o','a','a','n'],
['e','t','a','e'],
['i','h','k','r'],
['i','f','l','v']
]

Output: ["eat","oath"]
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
using TrieNode = struct TrieNode {
vector<TrieNode*> next;
string word;

TrieNode() {
next = vector<TrieNode*>(26, nullptr);
}
};

TrieNode* buildTrie(const vector<string>& dict) {
TrieNode* root = new TrieNode();

for (auto word : dict) {
TrieNode* p = root;
for (auto c : word) {
if (p->next[c-'a'] == nullptr) {
p->next[c-'a'] = new TrieNode();
}
p = p->next[c-'a'];
}
p->word = word;
}

return root;
}

void dfs(vector<vector<char>>& grid,
int sr,
int sc,
TrieNode* root,
vector<string>& res)
{
char c = grid[sr][sc];
auto p = root->next[c-'a'];
if (p == nullptr) return;
if (!p->word.empty()) {
res.push_back(p->word);
p->word = ""; // reset to avoid repeat result
}

int m = grid.size(), n = grid[0].size();
vector<pair<int,int>> dirs = {
{1, 0}, {0, 1}, {-1, 0}, {0, -1}
};
grid[sr][sc] = '#'; // avoid traverse back
for (auto dir : dirs) {
int i = sr + dir.first;
int j = sc + dir.second;
if (i < 0 || j < 0 || i == m || j == n || grid[i][j] == '#') continue;
dfs(grid, i, j, p, res);
}
grid[sr][sc] = c; // back to original grid

return;
}

vector<string> findWord(vector<vector<char>>& grid, const vector<string>& dict) {
vector<string> res;
if (grid.empty()) return res;
TrieNode* trie = buildTrie(dict);
for (int i = 0; i < grid.size(); i++) {
for (int j = 0; j < grid[0].size(); j++) {
dfs(grid, i, j, trie, res);
}
}
return res;
}