Leetcode|Leetcode 208:Implement Trie (Prefix Tree)
题目链接：
https://leetcode.com/problems/implement-trie-prefix-tree/description/
【Leetcode|Leetcode 208:Implement Trie (Prefix Tree)】字典树，常见到操作，插入，查找，是否是前缀。
参考的一段代码：
#include using namespace std;
class Trie{
public:
struct TrieNode
{
int cnt;
TrieNode *next[26];
//a-z
bool isword;
TrieNode()
{
cnt = 0;
isword = false;
for(int i=0;
i<26;
++i)
next[i] = NULL;
}
};
TrieNode *root;
Trie()
{
root = new TrieNode();
}
void insert(string word)
{
int slen = word.length();
TrieNode *p = root;
for(int i=0;
inext[cindex])
{
TrieNode *tnode = new TrieNode();
tnode->cnt = 1;
p->next[cindex]= tnode;
p = tnode;
}
else
{
p->next[cindex]->cnt += 1;
p = p->next[cindex];
}
}
p->isword = true;
}bool search(string word)
{
int slen = word.length();
TrieNode *p = root;
int i = 0;
for(;
inext[sindex])
break;
p = p->next[sindex];
}
if (i==slen)
return (p->isword);
return false;
}bool startsWith(string prefix)
{
int slen = prefix.length();
int i = 0;
TrieNode *p = root;
for(;
inext[prefix[i]-'a'])
break;
p = p->next[prefix[i]-'a'];
}
if(i!=slen)
return false;
return true;
}};
int main(int argc, char **argv)
{
Trie obj = Trie();
string word;
word = "Trie";
obj.insert(word);
word = "insert";
obj.insert(word);
word = "search";
obj.insert(word);
word = "startsWith";
obj.insert(word);
word = "a";
cout< 推荐阅读
- 【Leetcode/Python】001-Two|【Leetcode/Python】001-Two Sum
- leetcode|leetcode 92. 反转链表 II
- 二叉树路径节点关键值和等于目标值（LeetCode--112&LeetCode--113）
- LeetCode算法题-11.|LeetCode算法题-11. 盛最多水的容器（Swift）
- LeetCode（03）Longest|LeetCode（03）Longest Substring Without Repeating Characters
- Leetcode|Leetcode No.198打家劫舍
- [leetcode数组系列]1两数之和
- 数据结构和算法|LeetCode 的正确使用方式
- leetcode|今天开始记录自己的力扣之路
- LeetCode|LeetCode 876. 链表的中间结点