每日一题208 前缀树
文章目录
208. 实现 Trie (前缀树)
请你实现 Trie 类:
Trie()初始化前缀树对象。void insert(String word)向前缀树中插入字符串 word 。boolean search(String word)如果字符串 word 在前缀树中,返回 true(即,在检索之前已经插入);否则,返回 false 。boolean startsWith(String prefix)如果之前已经插入的字符串 word 的前缀之一为 prefix ,返回 true ;否则,返回 false 。
方法1
- 前缀树组成
class Trie {
private:
bool isEnd;//表示是否是最后一个字符
Trie *next[26];
};class Trie {
private:
bool isEnd;//表示是否是最后一个字符
Trie *next[26];
};
public:
Trie() {
isEnd = false;
memset(next, 0, sizeof(next));
}
void insert(String word) {
Trie *node = this;
for (char c:word) {
if (node->next[c-'a'] == NULL) {
node->next[c-'a'] = new Trie();
}
node = node->next[c-'a'];
}
node->isEnd = true;
}
boolean search(String word) {
Trie *node = this;
for (char c:word) {
if (node->next[c-'a'] == NULL) {
return false;
}
node = node->next[c-'a'];
}
return node->isEnd;
}
boolean startsWith(String prefix) {
Trie *node = this;
for (char c : prefix) {
node = node->next[c-'a'];
if (node == NULL) {
return false;
}
}
return true;
}
}
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论