208. Implement Trie (Prefix Tree)
字典樹（Trie，發音為 "try"）或前綴樹是一種樹形數據結構，用於高效地存儲和檢索字符串數據集中的鍵。這種數據結構有多種應用，如自動完成和拼寫檢查器。
實現 Trie 類：Trie() 初始化字典樹對象。
void insert(String word) 將字符串 word 插入到字典樹中。
boolean search(String word) 如果字典樹中包含字符串 word（即之前插入過），返回 true，否則返回 false。
boolean startsWith(String prefix) 如果字典樹中存在之前插入的字符串以 prefix 為前綴，返回 true，否則返回 false。
範例：
輸入["Trie", "insert", "search", "search", "startsWith", "insert", "search"] [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
輸出[null, null, true, false, true, null, true]
解釋Trie trie = new Trie(); trie.insert("apple"); trie.search("apple"); // 返回 true trie.search("app"); // 返回 false trie.startsWith("app"); // 返回 true trie.insert("app"); trie.search("app"); // 返回 true
Python
class TrieNode:
def __init__(self):
self.children = {}
self.is_end_of_word = False
class Trie:
def __init__(self):
"""
Initialize your data structure here.
"""
self.root = TrieNode()
def insert(self, word: str) -> None:
"""
Inserts a word into the trie.
"""
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_end_of_word = True
def search(self, word: str) -> bool:
"""
Returns if the word is in the trie.
"""
node = self.root
for char in word:
if char not in node.children:
return False
node = node.children[char]
return node.is_end_of_word
def startsWith(self, prefix: str) -> bool:
"""
Returns if there is any word in the trie that starts with the given prefix.
"""
node = self.root
for char in prefix:
if char not in node.children:
return False
node = node.children[char]
return True
30.96MB, 129ms
C++
#include <string>
#include <unordered_map>
using namespace std;
class TrieNode {
public:
unordered_map<char, TrieNode*> children;
bool is_end_of_word;
TrieNode() : is_end_of_word(false) {}
};
class Trie {
public:
Trie() {
root = new TrieNode();
}
void insert(string word) {
TrieNode* node = root;
for (char c : word) {
if (node->children.find(c) == node->children.end()) {
node->children[c] = new TrieNode();
}
node = node->children[c];
}
node->is_end_of_word = true;
}
bool search(string word) {
TrieNode* node = root;
for (char c : word) {
if (node->children.find(c) == node->children.end()) {
return false;
}
node = node->children[c];
}
return node->is_end_of_word;
}
bool startsWith(string prefix) {
TrieNode* node = root;
for (char c : prefix) {
if (node->children.find(c) == node->children.end()) {
return false;
}
node = node->children[c];
}
return true;
}
private:
TrieNode* root;
};
46.66MB, 61ms
Javascript
var TrieNode = function() {
this.children = {};
this.isEndOfWord = false;
};
var Trie = function() {
this.root = new TrieNode();
};
/**
* @param {string} word
* @return {void}
*/
Trie.prototype.insert = function(word) {
let node = this.root;
for (let char of word) {
if (!node.children[char]) {
node.children[char] = new TrieNode();
}
node = node.children[char];
}
node.isEndOfWord = true;
};
/**
* @param {string} word
* @return {boolean}
*/
Trie.prototype.search = function(word) {
let node = this.root;
for (let char of word) {
if (!node.children[char]) {
return false;
}
node = node.children[char];
}
return node.isEndOfWord;
};
/**
* @param {string} prefix
* @return {boolean}
*/
Trie.prototype.startsWith = function(prefix) {
let node = this.root;
for (let char of prefix) {
if (!node.children[char]) {
return false;
}
node = node.children[char];
}
return true;
};
68.50MB, 165ms
