每日一道leetcode（新学数据结构版）

208. 实现 Trie (前缀树) - 力扣（LeetCode）

题目

Trie（发音类似 "try"）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。

请你实现 Trie 类：

• Trie() 初始化前缀树对象。
• void insert(String word) 向前缀树中插入字符串 word 。
• boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
• boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。

示例：

输入
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
输出
[null, null, true, false, true, null, true]

解释
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // 返回 True
trie.search("app");     // 返回 False
trie.startsWith("app"); // 返回 True
trie.insert("app");
trie.search("app");     // 返回 True

提示：

• 1 <= word.length, prefix.length <= 2000
• word 和 prefix 仅由小写英文字母组成
• insert、search 和 startsWith 调用次数 总计 不超过 3 * 104 次

思路（以下思路是经过检索学习后得出，有一部分的构造方法超出我的知识面了，所以不看的话构造不出来）

1. 首先这个类本身并没有内置于C++中，需要自己构造。
2. 这个树的思路比较清楚，是个26叉树，因为其子节点分别都有可能是26个字母（除非存在某个字母不是英文单词的开头，不过显然应该不存在这种情况），然后它还要具有一个功能就是判断到达该节点时是不是组成了一个单词。
3. 有了这两个基本的点那么就需要构造前缀树的节点类：
   1. 定义一个bool类型变量作为是否是一个单词的判断，再每次插入完成后，对最后一个节点标记为单词位。
   2. 另外需要保存子节点的指针，这里我以为可以直接继续创建对象数组，但是查了一下发现C++仅支持定义自身类型的静态对象或者是对象的指针，所以其实还是对树节点的构造方式不够了解——那么就是构造一个TrieNode* children[26]即可。
   3. 以上都需声明为public类型，否则默认是private的，这样其他类就无法调用。
4. 接下来是操作逻辑：
   1. 初始化：现在Trie类中定义一个root的TrieNode*节点作为初始节点。
   2. 插入(insert)：从根节点和插入单词头开始顺序检查对应位置的单词是否在链中，若在就往下搜，若不在就对该子节点创建一个新的TrieNode对象。不断重复知道单词遍历完成，最后将当前达到的节点的isWord更新为true。
   3. 查找(search)：从根节点开始出发，根据待查找单词从头到尾的顺序顺链查找是否已经创建了对应的子节点对象，若是空指针，直接返回false。若遍历完整个单词了，需检查对应的到达节点的isWord是否为true。
   4. 查找前缀(startsWith)：和search的方法类似，但最后一步不需要判断isWord，只要能找到这，那么就一定是前缀，直接返回true即可。

代码实现

class TrieNode {public:bool isWord = false;TrieNode* children[26];
};
class Trie {
public:TrieNode* root;Trie() {root = new TrieNode();}void insert(string word) {TrieNode* cur = root;char c;for(int i = 0; i < word.length(); ++i) {c = int(word[i]-'a');if(cur->children[c] == nullptr) cur->children[c] = new TrieNode();cur = cur->children[c];}cur->isWord = true;}bool search(string word) {TrieNode* cur = root;char c;for(int i = 0; i < word.length(); ++i) {c = int(word[i]-'a');if(cur->children[c] == nullptr) return false;cur = cur->children[c];}return cur->isWord;}bool startsWith(string prefix) {TrieNode* cur = root;char c;for(int i = 0; i < prefix.length(); ++i) {c = int(prefix[i]-'a');if(cur->children[c] == nullptr) return false;cur = cur->children[c];}return true;}
};/*** Your Trie object will be instantiated and called as such:* Trie* obj = new Trie();* obj->insert(word);* bool param_2 = obj->search(word);* bool param_3 = obj->startsWith(prefix);*/

复杂度分析

• 时间复杂度：因为直接顺链查找即可，插入、查找、判断前缀的时间复杂度都是O(n)的，初始化的时间复杂度是O(1)的。
• 空间复杂度：设需要插入的字符串长度之和为L，那么最坏情况的空间复杂度就是26L，若扩展应用范围，如果不是26个字符，而是字符集规模为S，则空间复杂度为O(LS)。

题解

• 官解的节点的实现是内置的，将Trie类直接当成TrieNode使用，逻辑也是一致的，不过感觉这样写对于类的定义就很模糊，感觉有点dirty，树和节点还是分开定义比较好，不然属性展现的是节点的属性，函数却展现的是树的功能。——虽然代码量少了，但是可读性就差了，感觉不是个好实现。
• 官解有一个点很可取，判断前缀和查找的功能有很大程度的重合，是可以封装的，确实得锻炼锻炼对这种情况的直觉，避免写出太冗余的代码。
• 看了其他人的题解发现自己还是太死板了，直接用哈希表貌似很快就能秒了。
  • 首先存一个单词哈希表，然后每次插入定义一个循环存前缀哈希表，时间复杂度是一致的。但是空间复杂度小了，因为很多没出现的节点就不用另外保存了！
  • 还是聪明人多啊！