每日一题时间:
2020-04-14
题目链接: 208. 实现 Trie (前缀树) 官方题解链接: 实现 Trie (前缀树)
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
次解题思路: 该题是多叉树的一种应用
struct TrieNode {
bool isEnd;
vector<TrieNode *> child;
TrieNode() : isEnd(false), child(26, nullptr) {}
};
class Trie {
private:
TrieNode* root;
public:
/** Initialize your data structure here. */
Trie() {
root = new TrieNode();
}
/** Inserts a word into the trie. */
void insert(string word) {
TrieNode * cur = root;
for (auto c : word) {
if(cur->child[c - 'a'] == nullptr)
cur->child[c - 'a'] = new TrieNode();
cur = cur->child[c - 'a'];
}
cur->isEnd = true;
}
/** Returns if the word is in the trie. */
bool search(string word) {
TrieNode * cur = root;
for (auto c : word) {
cur = cur->child[c - 'a'];
if (cur == nullptr) return false;
}
return cur->isEnd;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
bool startsWith(string prefix) {
TrieNode * cur = root;
for (auto c : prefix) {
cur = cur->child[c - 'a'];
if (cur == nullptr) return false;
}
return true;
}
};
init
: O(1)
O(|S|)
,其中 |S|
是每次插入或查询的字符串的长度。O(|T|\cdot\Sigma)
|T|
为所有插入字符串的长度之和\Sigma
为字符集的大小,本题 \Sigma=26
解题思路: 二叉搜索树如果遍历结果为单调递增, 因此采用递归方法进行最小值计算(当前值与上一个值的差的最小值)
class Solution {
public:
void dfs(TreeNode* root, int& pre, int& ans) {
if (root == nullptr) {
return;
}
dfs(root->left, pre, ans);
if (pre == -1) {
pre = root->val;
} else {
ans = min(ans, root->val - pre);
pre = root->val;
}
dfs(root->right, pre, ans);
}
int minDiffInBST(TreeNode* root) {
int ans = INT_MAX, pre = -1;
dfs(root, pre, ans);
return ans;
}
};
init
: O(1)
O(|S|)
,其中 |S|
是每次插入或查询的字符串的长度。O(|T|\cdot\Sigma)
|T|
为所有插入字符串的长度之和\Sigma
为字符集的大小,本题 \Sigma=26
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。