当前位置： 面试刷题>> 实现 Trie (前缀树)(经典算法150题)
### 题目描述
实现一个 Trie（前缀树），也称为字典树或单词查找树，用于高效地存储和检索字符串数据集中的键。Trie 树是一种树形结构，其中的每个节点都代表一个字符串中的字符，从根节点到某一节点所经过的路径上所有字符连接起来，就是该节点对应的字符串。Trie 树常用于自动补全、拼写检查、IP 路由等领域。
#### Trie 树的基本操作：
1. **插入（Insert）**：向 Trie 树中插入一个新的字符串。
2. **搜索（Search）**：检查 Trie 树中是否存在一个完整的字符串。
3. **前缀搜索（StartsWith）**：检查 Trie 树中是否存在某个前缀。
### 示例代码
#### PHP 实现
```php
class TrieNode {
public $children = [];
public $isEndOfWord = false;
public function __construct() {
$this->children = array_fill(0, 26, null); // 假设只处理小写字母
}
}
class Trie {
private $root;
public function __construct() {
$this->root = new TrieNode();
}
// 插入
public function insert($word) {
$node = $this->root;
for ($i = 0; $i < strlen($word); $i++) {
$index = ord($word[$i]) - ord('a');
if (!isset($node->children[$index])) {
$node->children[$index] = new TrieNode();
}
$node = $node->children[$index];
}
$node->isEndOfWord = true;
}
// 搜索
public function search($word) {
$node = $this->searchPrefix($word);
return $node !== null && $node->isEndOfWord;
}
// 前缀搜索
public function startsWith($prefix) {
return $this->searchPrefix($prefix) !== null;
}
// 辅助函数：搜索前缀
private function searchPrefix($word) {
$node = $this->root;
for ($i = 0; $i < strlen($word); $i++) {
$index = ord($word[$i]) - ord('a');
if (!isset($node->children[$index])) {
return null;
}
$node = $node->children[$index];
}
return $node;
}
}
// 使用示例
$trie = new Trie();
$trie->insert("apple");
echo $trie->search("apple") ? "Found" : "Not found"; // 输出: Found
echo $trie->startsWith("app") ? "Starts with 'app'" : "Does not start with 'app'"; // 输出: Starts with 'app'
```
#### Python 实现
```python
class TrieNode:
def __init__(self):
self.children = {}
self.is_end_of_word = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word: str) -> None:
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:
node = self.searchPrefix(word)
return node is not None and node.is_end_of_word
def startsWith(self, prefix: str) -> bool:
return self.searchPrefix(prefix) is not None
def searchPrefix(self, word: str) -> TrieNode:
node = self.root
for char in word:
if char not in node.children:
return None
node = node.children[char]
return node
# 使用示例
trie = Trie()
trie.insert("apple")
print(trie.search("apple")) # 输出: True
print(trie.startsWith("app")) # 输出: True
```
#### JavaScript 实现
```javascript
class TrieNode {
constructor() {
this.children = {};
this.isEndOfWord = false;
}
}
class Trie {
constructor() {
this.root = new TrieNode();
}
insert(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;
}
search(word) {
let node = this.searchPrefix(word);
return node !== null && node.isEndOfWord;
}
startsWith(prefix) {
return this.searchPrefix(prefix) !== null;
}
searchPrefix(word) {
let node = this.root;
for (let char of word) {
if (!node.children[char]) {
return null;
}
node = node.children[char];
}
return node;
}
}
// 使用示例
const trie = new Trie();
trie.insert("apple");
console.log(trie.search("apple")); // 输出: true
console.log(trie.startsWith("app")); // 输出: true
```
这些示例展示了如何在 PHP、Python 和 JavaScript 中实现 Trie 树，并提供了基本的插入、搜索和前缀搜索功能。在面试中，能够根据需求清晰、准确地编写出 Trie 树的实现代码，将体现出你的编程能力和数据结构知识的掌握程度。