莆田自助建站软件,黑客钓鱼网站的制作,德维尔全屋定制官方网站,红河优才网站建设Every day a Leetcode
题目来源#xff1a;211. 添加与搜索单词 - 数据结构设计
解法1#xff1a;字典树
字典树#xff08;前缀树#xff09;是一种树形数据结构#xff0c;用于高效地存储和检索字符串数据集中的键。前缀树可以用 O(∣S∣) 的时间复杂度完成如下操作…Every day a Leetcode
题目来源211. 添加与搜索单词 - 数据结构设计
解法1字典树
字典树前缀树是一种树形数据结构用于高效地存储和检索字符串数据集中的键。前缀树可以用 O(∣S∣) 的时间复杂度完成如下操作其中 ∣S∣ 是插入字符串或查询前缀的长度
向字典树中插入字符串 word查询字符串 word 是否已经插入到字典树中。
根据题意WordDictionary 类需要支持添加单词和搜索单词的操作可以使用字典树实现。
对于添加单词将单词添加到字典树中即可。
对于搜索单词从字典树的根结点开始搜索。由于待搜索的单词可能包含点号因此在搜索过程中需要考虑点号的处理。对于当前字符是字母和点号的情况分别按照如下方式处理 如果当前字符是字母则判断当前字符对应的子结点是否存在如果子结点存在则移动到子结点继续搜索下一个字符如果子结点不存在则说明单词不存在返回 false 如果当前字符是点号由于点号可以表示任何字母因此需要对当前结点的所有非空子结点继续搜索下一个字符。
重复上述步骤直到返回 false 或搜索完给定单词的最后一个字符。
如果搜索完给定的单词的最后一个字符则当搜索到的最后一个结点的 isEnd 为 true 时给定的单词存在。
特别地当搜索到点号时只要存在一个非空子结点可以搜索到给定的单词即返回 true 。
代码
/** lc appleetcode.cn id211 langcpp** [211] 添加与搜索单词 - 数据结构设计*/// lc codestart
struct TrieNode
{vectorTrieNode * child;bool isEnd;TrieNode() : child(vectorTrieNode *(26, nullptr)), isEnd(false) {}
};void insert(TrieNode *root, const string word)
{TrieNode *node root;for (const char c : word){if (node-child[c - a] nullptr)node-child[c - a] new TrieNode();node node-child[c - a];}node-isEnd true;
}class WordDictionary
{
private:TrieNode *trie;public:WordDictionary() : trie(new TrieNode()) {}void addWord(string word){insert(trie, word);}bool search(string word){return dfs(word, 0, trie);}bool dfs(const string word, int index, TrieNode *node){if (index word.size())return node-isEnd;char ch word[index];if (ch a ch z){TrieNode *child node-child[ch - a];if (child ! nullptr dfs(word, index 1, child))return true;}else if (ch .){for (int i 0; i 26; i){TrieNode *child node-child[i];if (child ! nullptr dfs(word, index 1, child))return true;}}return false;}
};/*** Your WordDictionary object will be instantiated and called as such:* WordDictionary* obj new WordDictionary();* obj-addWord(word);* bool param_2 obj-search(word);*/
// lc codeend结果 复杂度分析
时间复杂度初始化为 O(1)添加单词为 O(∣S∣)搜索单词为 O(∣Σ∣∣S∣)其中 ∣S∣ 是每次添加或搜索的单词的长度Σ 是字符集这道题中的字符集为全部小写英语字母∣Σ∣26。
空间复杂度O(∣T∣⋅∣Σ∣)其中 ∣T∣ 是所有添加的单词的长度之和Σ 是字符集这道题中的字符集为全部小写英语字母∣Σ∣26。
