php 企业网站模板 想1,建设工程合同印花税计税依据,注册网址怎么注册,做网站很忙吗题目分析
这道题让我们实现一个 Trie 类#xff08;也称为前缀树#xff09;#xff0c;以便高效地插入和查询字符串。前缀树是一种特殊的树形数据结构#xff0c;适用于快速存储和检索字符串数据集中的键#xff0c;比如实现 自动补全 和 拼写检查。
题目要求
Trie 类…题目分析
这道题让我们实现一个 Trie 类也称为前缀树以便高效地插入和查询字符串。前缀树是一种特殊的树形数据结构适用于快速存储和检索字符串数据集中的键比如实现 自动补全 和 拼写检查。
题目要求
Trie 类中有以下几个方法
Trie(): 初始化前缀树对象。insert(String word): 向前缀树中插入一个字符串 word。search(String word): 如果前缀树中包含 word返回 true否则返回 false。startsWith(String prefix): 如果前缀树中存在以 prefix 为前缀的字符串则返回 true否则返回 false。
解题思路
为了解决这个问题我们可以按照以下步骤来思考 Trie 数据结构前缀树用来存储字符串字符间的共享前缀会共用路径以减少空间消耗并提高查询效率。每个节点代表一个字符树的根节点为空节点。沿着从根节点出发的路径到叶节点的字符组合表示存储的字符串。 TrieNode 类设计前缀树中的每个节点可以使用一个 TrieNode 类来表示。每个 TrieNode 保存两个信息 子节点列表存储连接到当前节点的其他字符。结束标志用于标记当前节点是否是一个单词的结尾。 Trie 类设计前缀树本身实现插入、查找和前缀匹配等功能。需要在 Trie 类中实现以下方法 插入insert从根节点开始逐字符插入如果字符节点不存在就创建新节点最后一个字符节点标记为单词结尾。查找search从根节点出发逐字符查找直到找到整个单词或发现单词不存在。前缀匹配startsWith类似查找只需检查前缀是否存在即可。
实现代码
以下是 Trie 类的 C 实现包含插入、查找和前缀匹配功能。
#include iostream
#include unordered_map
#include stringclass TrieNode {
public:bool isEndOfWord; // 标记当前节点是否为一个单词的结尾std::unordered_mapchar, TrieNode* children; // 用于存储子节点TrieNode() : isEndOfWord(false) {} // 构造函数初始化
};class Trie {
private:TrieNode* root;public:Trie() {root new TrieNode(); // 初始化 Trie根节点为空节点}// 插入字符串void insert(const std::string word) {TrieNode* node root;for (char ch : word) {if (node-children.find(ch) node-children.end()) {node-children[ch] new TrieNode(); // 如果子节点不存在则创建}node node-children[ch]; // 移动到下一个子节点}node-isEndOfWord true; // 最后一个节点标记为单词结尾}// 查找字符串bool search(const std::string word) const {TrieNode* node root;for (char ch : word) {if (node-children.find(ch) node-children.end()) {return false; // 如果字符节点不存在返回 false}node node-children[ch]; // 移动到下一个子节点}return node-isEndOfWord; // 判断是否为单词结尾}// 查找前缀bool startsWith(const std::string prefix) const {TrieNode* node root;for (char ch : prefix) {if (node-children.find(ch) node-children.end()) {return false; // 如果前缀节点不存在返回 false}node node-children[ch]; // 移动到下一个子节点}return true; // 所有字符都找到返回 true}
};示例讲解
假设我们运行以下代码
Trie trie Trie();
trie.insert(apple);
std::cout trie.search(apple) std::endl; // 返回 true
std::cout trie.search(app) std::endl; // 返回 false
std::cout trie.startsWith(app) std::endl; // 返回 true
trie.insert(app);
std::cout trie.search(app) std::endl; // 返回 true执行步骤
为了更具象地展示前缀树的构建过程我们可以用图形化的方式模拟每一步的节点构造。
1. 初始化 Trie
Trie trie Trie();创建了一个 Trie 对象。此时只有一个根节点根节点本身是空的不保存任何字符内容。
2. 插入字符串 apple
trie.insert(apple);在插入 apple 时前缀树会按字符逐个插入a - p - p - l - e。详细步骤如下 第一步根节点开始插入字符 a。根节点没有子节点 a于是创建一个节点表示 a 并加入子节点。 (root)|a第二步在 a 节点下插入字符 p。节点 a 没有子节点 p创建并添加节点表示 p。 (root)|a|p第三步继续在 p 节点下插入字符 p。节点 p 没有子节点 p创建并添加节点表示 p。 (root)|a|p|p第四步继续在第二个 p 节点下插入字符 l。节点 p 没有子节点 l创建并添加节点表示 l。 (root)|a|p|p|l第五步在 l 节点下插入字符 e。节点 l 没有子节点 e创建并添加节点表示 e并将其标记为单词结尾 (isEndOfWord true)。 (root)|a|p|p|l|e (end)到此为止我们已经成功将 apple 插入到了前缀树中。apple 的路径为a - p - p - l - e。
3. 查找 apple
trie.search(apple);从根节点逐字符查找 a - p - p - l - e。遇到节点 e并且 e 被标记为单词的结尾 (isEndOfWord true)因此返回 true。
4. 查找 app
trie.search(app);从根节点逐字符查找 a - p - p。到达最后一个 p 节点但它没有被标记为单词的结尾isEndOfWord false表示 app 虽然存在路径但不是一个完整的单词因此返回 false。
5. 查找前缀 app
trie.startsWith(app);从根节点逐字符查找 a - p - p。找到 app 路径中的所有字符所以返回 true 表示 app 是某个单词的前缀。
6. 插入 app
trie.insert(app);这次插入 app 的过程如下 从根节点逐字符插入 a - p - p。 到达最后一个 p 节点因为节点已存在无需再创建节点。只需将该节点标记为单词结尾 (isEndOfWord true)。 (root)|a|p|p (end)|l|e (end)现在 app 路径已标记为一个完整的单词。
7. 查找 app 再次验证
trie.search(app);从根节点逐字符查找 a - p - p。找到 p 节点且 p 已标记为单词的结尾 (isEndOfWord true)因此返回 true 表示 app 存在。
图示总结
通过逐字符的插入和标记我们最终得到了如下的前缀树结构 (root)|a|p|p (end)|l|e (end)app 是一条有效路径以 p (end) 为结尾。apple 是另一条有效路径以 e (end) 为结尾。
小结
插入过程逐字符插入每次检查是否存在子节点不存在则创建。单词结尾的字符节点会被标记为 isEndOfWord true。查找过程逐字符查找直到找到整个单词路径。如果路径末尾的节点标记为单词结尾则该单词存在。前缀查找逐字符查找路径中的前缀只需验证路径存在不要求路径末尾节点为单词结尾。
这种树形结构使得共享前缀的单词复用相同路径节省存储空间并提高了查询效率。
复杂度分析
时间复杂度 插入O(m)其中 m 为字符串的长度。查找O(m)。前缀查找O(m)。 空间复杂度插入 N 个字符串每个长度为 m最坏情况下空间复杂度为 O(N * m)但由于前缀共享这个复杂度会降低。
好的让我们通过更加通俗、易于理解的语言来解释 自动补全 和 拼写检查 的实现过程便于大家理解。 应用场景
自动补全和拼写检查是前缀树Trie的两个经典应用它们都需要在大量单词中快速查找具有相同前缀或类似拼写的单词。前缀树的结构使得这些功能可以在短时间内完成。
1. 自动补全
自动补全主要用于在用户输入一部分单词前缀时推荐以该前缀开头的完整单词。例如当用户输入 app 时系统希望能迅速推荐像 apple、application 这样的词。
自动补全的步骤 第一步查找前缀 通过 startsWith 方法从根节点开始按用户输入的前缀逐字符向下查找。如果每个字符都能在前缀树中找到说明该前缀存在否则表示 Trie 中没有以该前缀开头的单词。 第二步找出所有可能的单词 一旦找到前缀的最后一个字符节点接下来就是从这个节点开始通过深度优先遍历DFS或广度优先遍历BFS找到所有以这个前缀开头的单词。在遍历过程中只要遇到节点被标记为一个完整单词的结尾就可以将当前路径组合成一个单词加入到推荐结果中。
示例
假设前缀树中存有 apple、app、application、apply 等单词。当用户输入 app 时系统将
使用 startsWith 方法查找前缀 app确认前缀存在。从最后的 p 节点开始遍历其子节点逐一找到以 app 开头的完整单词apple、application 和 apply。
这就是自动补全的基本过程最终返回以 app 为开头的推荐单词。 2. 拼写检查
拼写检查用于纠正用户的拼写错误。当用户输入单词时如果单词不存在拼写检查会推荐一些拼写相似的正确单词。这里使用前缀树来检查是否存在某个单词并生成近似的拼写推荐。
拼写检查的步骤 第一步检查单词是否存在 使用 search 方法直接在前缀树中查找用户输入的单词。如果找到说明拼写正确如果找不到则需要生成拼写相似的候选词。 第二步生成近似候选词 如果单词不存在我们就使用一些简单的修改方式生成可能的“拼写相近”的词然后逐一在前缀树中查找看看哪些单词存在。常用的修改方式包括 替换字符将单词中的某个字母替换为其他字母生成新单词并查找。例如将 appl 中的最后一个字符替换为 e生成 apple。删除字符尝试删除单词的某个字符生成新单词并查找。例如删除 appl 中的最后一个字符生成 app。添加字符尝试在某个位置插入一个新字符生成新单词并查找。例如在 appl 后添加 e生成 apple。交换字符尝试交换单词中的相邻字符生成新单词并查找。
示例
假设用户输入了 appl少了一个字母 e。Trie 会先尝试直接查找 appl发现不存在然后生成近似词进行查找
尝试添加字符 e生成 apple在 Trie 中找到了该单词。也可以通过删除字符生成 app在 Trie 中也存在。
最终拼写检查可以将 apple 和 app 作为拼写建议返回给用户。
总结
这道题中的 Trie 数据结构为我们提供了一种快速存储和查询大量字符串的方法特别适合具有公共前缀的字符串。通过这种数据结构可以高效地完成自动补全、拼写检查等操作。在实现过程中我们使用了 TrieNode 和 Trie 类分别表示节点和整个前缀树采用 unordered_map 存储子节点关系实现了 O(m) 时间复杂度的插入和查找功能。
