当前位置： 面试刷题>> 字典树(经典算法150题)
### 题目描述补充
题目：**实现一个字典树（Trie）数据结构，并提供插入、搜索和前缀搜索功能**
字典树（Trie），又称前缀树或单词查找树，是一种树形结构，用于高效地存储和检索字符串数据集中的字符串。在字典树中，每个节点代表一个字符串的某个前缀，从根到任意节点的路径所组成的字符串对应于该节点所代表的字符串。
#### 功能要求：
1. **插入（Insert）**：向字典树中插入一个字符串。
2. **搜索（Search）**：在字典树中搜索一个完整的字符串，如果找到则返回true，否则返回false。
3. **前缀搜索（StartsWith）**：在字典树中搜索一个字符串的前缀，如果存在任何以该前缀开头的字符串，则返回true，否则返回false。
#### 示例
假设我们有以下字符串集合：{"apple", "app", "banana", "band"}
- 插入："apple", "app", "banana", "band"
- 搜索："app" 应返回 true
- 搜索："cat" 应返回 false
- 前缀搜索："ban" 应返回 true，因为存在 "banana" 和 "band"
### PHP 代码示例
```php
class TrieNode {
public $children = [];
public $isEndOfWord = false;
function __construct() {
$this->children = array_fill(0, 26, null);
}
}
class Trie {
private $root;
function __construct() {
$this->root = new TrieNode();
}
function insert($word) {
$node = $this->root;
for ($i = 0; $i < strlen($word); $i++) {
$char = ord($word[$i]) - ord('a');
if (!isset($node->children[$char])) {
$node->children[$char] = new TrieNode();
}
$node = $node->children[$char];
}
$node->isEndOfWord = true;
}
function search($word) {
$node = $this->searchPrefix($word);
return $node !== null && $node->isEndOfWord;
}
function startsWith($prefix) {
$node = $this->searchPrefix($prefix);
return $node !== null;
}
private function searchPrefix($word) {
$node = $this->root;
for ($i = 0; $i < strlen($word); $i++) {
$char = ord($word[$i]) - ord('a');
if (!isset($node->children[$char])) {
return null;
}
$node = $node->children[$char];
}
return $node;
}
}
// 使用示例
$trie = new Trie();
$trie->insert("apple");
echo $trie->search("app") ? "true" : "false"; // false
echo $trie->startsWith("app") ? "true" : "false"; // true
```
### 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):
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):
node = self.search_prefix(word)
return node is not None and node.is_end_of_word
def starts_with(self, prefix):
return self.search_prefix(prefix) is not None
def search_prefix(self, word):
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("app")) # False
print(trie.starts_with("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("app")); // false
console.log(trie.startsWith("app")); // true
```
希望这些示例能帮助你理解并实现字典树数据结构。在码小课网站上发布时，记得保持内容的清晰和逻辑连贯。