实现 Trie (前缀树)
图解：
.jpg "实现 Trie (前缀树)")
应用：
-
在工程中，不考虑前缀匹配的话，基本上使用 hash 就能满足；
-
如果考虑前缀匹配的话，工程也不会使用 Trie：
- 一方面是字符集大小不好确定（题目只考虑 26 个字母，字符集大小限制在较小的 26 内）因此可以使用 Trie，但是工程一般兼容各种字符集，一旦字符集大小很大的话，Trie 将会带来很大的空间浪费；
- 另外，对于个别的超长字符 Trie 会进一步变深；
- 这时候如果 Trie 是存储在硬盘中，Trie 结构过深带来的影响是多次随机 IO，随机 IO 是成本很高的操作；
-
同时 Trie 的特殊结构，也会为分布式存储将会带来困难；
-
因此在工程领域中 Trie 的应用面不广；
代码实现：
class Trie {
children: { end?: boolean } | null;
constructor() {
this.children = {};
}
insert(word: string): void {
let children = this.children;
for (let ch of word) {
if (!children[ch]) {
children[ch] = {};
}
children = children[ch];
}
children.end = true; // 最后一个节点标记一下结束
}
private searchPrefix(prefix) {
let { children } = this;
for (const ch of prefix) {
if (!children[ch]) {
return false;
}
children = children[ch];
}
return children;
}
search(word: string): boolean {
let ret = this.searchPrefix(word);
return ret && ret.end !== undefined;
}
startsWith(prefix: string): boolean {
return !!this.searchPrefix(prefix);
}
}
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 502. IPO
上一篇
评论
