当前位置： 面试刷题>> 添加与搜索单词 - 数据结构设计(经典算法150题)
### 题目描述
设计一个数据结构，支持添加字符串和搜索字符串中的前缀或任意子串的功能。具体地说，你需要实现以下功能：
1. **`addWord(word)`**：向数据结构中添加一个单词。
2. **`search(word)`**：返回单词是否可以在数据结构中的某个单词里找到。单词中的字母顺序可以被打乱。
3. **`startsWith(prefix)`**：返回是否有任何单词以给定的前缀开始。
### 示例
假设我们有以下操作：
```
Trie trie = new Trie();
trie.addWord("hello");
trie.addWord("world");
trie.search("world"); // 返回 true
trie.search("word"); // 返回 false
trie.startsWith("wor"); // 返回 true
trie.startsWith("wo"); // 返回 false
trie.search("hell"); // 返回 false
trie.search(""); // 返回 false（空字符串不被视为单词）
```
### 解题思路
为了实现这个功能，我们可以使用**Trie（前缀树）**结合**集合（Set）**来存储每个单词的字符的所有排列。具体来说，对于每个添加到Trie中的单词，我们可以生成其所有字符的排列，并将这些排列存储在Trie节点对应的集合中。然而，这种方法的空间复杂度会非常高。
为了优化空间复杂度，我们可以采用一个更巧妙的方法：在Trie的每个节点上，除了存储子节点指针外，还存储一个布尔数组或位集合（bitset），用于表示当前节点下是否可以形成某个特定长度的单词（不考虑顺序）。对于`startsWith`操作，我们只需遍历Trie直到前缀的最后一个字符即可。对于`search`操作，我们需要在Trie中找到一个路径，使得路径上的节点能够构成给定单词的所有字符（不考虑顺序），这通常涉及到更复杂的逻辑或额外的数据结构。
但为简化实现，以下示例代码将只展示使用Trie结构实现`addWord`和`startsWith`功能，并假设`search`操作需要额外的数据结构或逻辑来支持乱序搜索（这里不展开）。
### PHP 示例代码
```php
class TrieNode {
public $children = [];
public $isEndOfWord = false;
public $startsWithPrefix = false;
public function __construct() {
$this->children = array_fill(0, 26, null);
}
}
class Trie {
private $root;
function __construct() {
$this->root = new TrieNode();
}
function addWord($word) {
$node = $this->root;
$node->startsWithPrefix = true; // Mark root as starting point
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->startsWithPrefix = true; // Mark each node in path as part of some prefix
if ($i == strlen($word) - 1) {
$node->isEndOfWord = true;
}
}
}
function startsWith($prefix) {
$node = $this->root;
for ($i = 0; $i < strlen($prefix); $i++) {
$index = ord($prefix[$i]) - ord('a');
if (!isset($node->children[$index]) || !$node->children[$index]->startsWithPrefix) {
return false;
}
$node = $node->children[$index];
}
return true;
}
}
```
请注意，上述PHP代码实现了`addWord`和`startsWith`功能，但没有实现完整的`search`功能以支持乱序搜索。对于`search`功能的完整实现，您可能需要引入额外的数据结构或逻辑来处理字符的乱序问题。
类似地，Python和JavaScript的实现逻辑会非常相似，只是语法和库的使用上会有所不同。