第五章 - 高频考题(中等)
1906. 查询差绝对值的最小值
0208. 实现 Trie (前缀树)

题目地址(208. 实现 Trie (前缀树))

题目描述

1
实现一个 Trie (前缀树),包含 insert, search, 和 startsWith 这三个操作。
2
3
示例:
4
5
Trie trie = new Trie();
6
7
trie.insert("apple");
8
trie.search("apple"); // 返回 true
9
trie.search("app"); // 返回 false
10
trie.startsWith("app"); // 返回 true
11
trie.insert("app");
12
trie.search("app"); // 返回 true
13
说明:
14
15
你可以假设所有的输入都是由小写字母 a-z 构成的。
16
保证所有输入均为非空字符串。
Copied!

前置知识

公司

  • 阿里
  • 腾讯
  • 百度
  • 字节

思路

这是一道很直接的题目,上来就让你实现前缀树(字典树)。这算是基础数据结构中的 知识了,不清楚什么是字典树的可以查阅相关资料。
我们看到题目给出的使用方法new Trie, insert,searchstartWith.
为了区分searchstartWith我们需要增加一个标示来区分当前节点是否是某个单词的结尾。 因此节点的数据结构应该是:
1
function TrieNode(val) {
2
this.val = val; // 当前的字母
3
this.children = []; // 题目要求字典仅有a-z,那么其长度最大为26(26个字母)
4
this.isWord = false;
5
}
Copied!
每次 insert 我们其实都是从根节点出发,一个一个找到我们需要添加的节点,修改 children 的值.
我们应该修改哪一个 child 呢? 我们需要一个函数来计算索引
1
function computeIndex(c) {
2
return c.charCodeAt(0) - "a".charCodeAt(0);
3
}
Copied!
其实不管 insert, search 和 startWith 的逻辑都是差不多的,都是从 root 出发, 找到我们需要操作的 child, 然后进行相应操作(添加,修改,返回)。
208.implement-trie-prefix-tree-1

关键点解析

  • 前缀树

代码

1
/*
2
* @lc app=leetcode id=208 lang=javascript
3
*
4
* [208] Implement Trie (Prefix Tree)
5
*
6
* https://leetcode.com/problems/implement-trie-prefix-tree/description/
7
*
8
* algorithms
9
* Medium (36.93%)
10
* Total Accepted: 172K
11
* Total Submissions: 455.5K
12
* Testcase Example: '["Trie","insert","search","search","startsWith","insert","search"]\n[[],["apple"],["apple"],["app"],["app"],["app"],["app"]]'
13
*
14
* Implement a trie with insert, search, and startsWith methods.
15
*
16
* Example:
17
*
18
*
19
* Trie trie = new Trie();
20
*
21
* trie.insert("apple");
22
* trie.search("apple"); // returns true
23
* trie.search("app"); // returns false
24
* trie.startsWith("app"); // returns true
25
* trie.insert("app");
26
* trie.search("app"); // returns true
27
*
28
*
29
* Note:
30
*
31
*
32
* You may assume that all inputs are consist of lowercase letters a-z.
33
* All inputs are guaranteed to be non-empty strings.
34
*
35
*
36
*/
37
function TrieNode(val) {
38
this.val = val;
39
this.children = [];
40
this.isWord = false;
41
}
42
43
function computeIndex(c) {
44
return c.charCodeAt(0) - "a".charCodeAt(0);
45
}
46
/**
47
* Initialize your data structure here.
48
*/
49
var Trie = function () {
50
this.root = new TrieNode(null);
51
};
52
53
/**
54
* Inserts a word into the trie.
55
* @param {string} word
56
* @return {void}
57
*/
58
Trie.prototype.insert = function (word) {
59
let ws = this.root;
60
for (let i = 0; i < word.length; i++) {
61
const c = word[i];
62
const current = computeIndex(c);
63
if (!ws.children[current]) {
64
ws.children[current] = new TrieNode(c);
65
}
66
ws = ws.children[current];
67
}
68
ws.isWord = true;
69
};
70
71
/**
72
* Returns if the word is in the trie.
73
* @param {string} word
74
* @return {boolean}
75
*/
76
Trie.prototype.search = function (word) {
77
let ws = this.root;
78
for (let i = 0; i < word.length; i++) {
79
const c = word[i];
80
const current = computeIndex(c);
81
if (!ws.children[current]) return false;
82
ws = ws.children[current];
83
}
84
return ws.isWord;
85
};
86
87
/**
88
* Returns if there is any word in the trie that starts with the given prefix.
89
* @param {string} prefix
90
* @return {boolean}
91
*/
92
Trie.prototype.startsWith = function (prefix) {
93
let ws = this.root;
94
for (let i = 0; i < prefix.length; i++) {
95
const c = prefix[i];
96
const current = computeIndex(c);
97
if (!ws.children[current]) return false;
98
ws = ws.children[current];
99
}
100
return true;
101
};
102
103
/**
104
* Your Trie object will be instantiated and called as such:
105
* var obj = new Trie()
106
* obj.insert(word)
107
* var param_2 = obj.search(word)
108
* var param_3 = obj.startsWith(prefix)
109
*/
Copied!

相关题目