注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

HT·生活

123

 
 
 

日志

 
 

ex208 Implement Trie (Prefix Tree)  

2015-05-24 21:05:46|  分类: leetcode |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

Implement a trie with insertsearch, and startsWith methods.

Note:
You may assume that all inputs are consist of lowercase letters a-z.


首先得搞清楚什么是prefix tree,他是一种26叉树,因为是为了更节省空间地存储字典,也就是说比如两个单词前缀一样,他们前面相同的只需要存一遍就可以了。因为英文单词有26个,所以每一步都有26个分支,如果字典序足够大的话。先看一张图
ex208 Implement Trie (Prefix Tree) - HT - HT·生活
 
上面的树中,tea和ted,就是前面的相同,直接存后面不同的就可以了。如下代码,代码不是我写的,对于这种数据结构,整明白了就可以了,后面用的时候也把这个好好熟悉了一遍,在ex211里面我重点修改了一下

class TrieNode {
private:
TrieNode *next[26];
bool ed;
public:
// Initialize your data structure here.
TrieNode() {
//每棵树可能有26个分支
memset(next, 0, sizeof(TrieNode *) * 26);
ed = false;
}
TrieNode *insert(char ch) {
int p = ch - 'a';
return next[p] = new TrieNode();
}
TrieNode *get(char ch) {
int p = ch - 'a';
return next[p];
}
void seted(bool val) {
ed = val;
}
bool geted() {
return ed;
}
};

class Trie {
public:
Trie() {
root = new TrieNode();
}

// Inserts a word into the trie.
void insert(string s) {
TrieNode *r = root;
for (int i = 0; i < s.length(); ++i) {
TrieNode *p = r->get(s[i]);
if (!p) {
p = r->insert(s[i]);
}
r = p;
}
r->seted(true);
}

// Returns if the word is in the trie.
bool search(string key) {
TrieNode *r = root;
for (int i = 0; i < key.length(); ++i) {
r = r->get(key[i]);
if (!r) return false;
}
return r->geted();
}

// Returns if there is any word in the trie
// that starts with the given prefix.
bool startsWith(string prefix) {
TrieNode *r = root;
for (int i = 0; i < prefix.length(); ++i) {
r = r->get(prefix[i]);
if (!r) return false;
}
return true;
}

private:
TrieNode* root;
};

// Your Trie object will be instantiated and called as such:
// Trie trie;
// trie.insert("somestring");
// trie.search("key");





参考
http://blog.csdn.net/bachelorchen/article/details/45576535
http://blog.csdn.net/beiyetengqing/article/details/7856113
http://blog.csdn.net/jia_xiaoxin/article/details/2914231
  评论这张
 
阅读(6)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017