当前位置： 面试刷题>> 实现前缀树(Trie) (经典算法题500道)
### 题目描述补充
题目：实现一个前缀树（Trie，又称字典树、单词查找树或键树），用于高效存储和检索字符串数据集中的键。前缀树是一种树形数据结构，其中的每个节点代表字符串中的一个字符。树的根节点不包含字符，除根节点外的每个节点都包含一个字符。从根节点到某个节点的路径上的字符连接起来，就是该节点对应的字符串。前缀树支持以下几种基本操作：
1. **插入**：向前缀树中插入一个新的字符串。
2. **搜索**：在前缀树中搜索一个完整的字符串。
3. **前缀搜索**：在前缀树中搜索一个字符串的前缀，返回所有以该前缀开头的字符串。
### 示例代码
以下是使用 PHP、Python 和 JavaScript 实现的前缀树的基本框架和示例代码。
#### PHP 示例
```php
class TrieNode {
public $children = [];
public $isEndOfWord = false;
public function __construct() {
$this->children = [];
$this->isEndOfWord = false;
}
}
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++) {
$char = $word[$i];
if (!isset($node->children[$char])) {
$node->children[$char] = new TrieNode();
}
$node = $node->children[$char];
}
$node->isEndOfWord = true;
}
// 搜索字符串
public function search($word) {
$node = $this->root;
for ($i = 0; $i < strlen($word); $i++) {
$char = $word[$i];
if (!isset($node->children[$char])) {
return false;
}
$node = $node->children[$char];
}
return $node->isEndOfWord;
}
// 前缀搜索
public function startsWith($prefix) {
$node = $this->root;
for ($i = 0; $i < strlen($prefix); $i++) {
$char = $prefix[$i];
if (!isset($node->children[$char])) {
return false;
}
$node = $node->children[$char];
}
return true;
}
}
// 使用示例
$trie = new Trie();
$trie->insert("apple");
echo $trie->search("apple") ? "Found" : "Not found"; // 输出 "Found"
echo $trie->startsWith("app") ? "Starts with 'app'" : "Not starts 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.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:
node = self.root
for char in prefix:
if char not in node.children:
return False
node = node.children[char]
return True
# 使用示例
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.root;
for (let char of word) {
if (!node.children[char]) {
return false;
}
node = node.children[char];
}
return node.isEndOfWord;
}
startsWith(prefix) {
let node = this.root;
for (let char of prefix) {
if (!node.children[char]) {
return false;
}
node = node.children[char];
}
return true;
}
}
// 使用示例
const trie = new Trie();
trie.insert("apple");
console.log(trie.search("apple")); // 输出 true
console.log(trie.startsWith("app")); // 输出 true
```
### 码小课
码小课网站中有更多关于算法和数据结构的内容分享，包括前缀树（Trie）的深入解析和进阶应用，欢迎大家学习交流。