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

HT·生活

123

 
 
 

日志

 
 

ex211 Add and Search Word - Data structure design  

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

  下载LOFTER 我的照片书  |

Design a data structure that supports the following two operations:

void addWord(word)
bool search(word)

search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.

For example:

addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true

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



就是一种正则表达式的匹配,用到上面的prefix tree的数据结构了,原始的prefix tree用的是顺序搜索,这里需要用到递归,而且有的地方可能有26个分支,需要单独考虑'.'的字符匹配的问题。如下

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];
}
TrieNode *get(int index) {
return next[index];
}
void seted(bool val) {
ed = val;
}
bool geted() {
return ed;
}
};

class WordDictionary {
private:
TrieNode* root;
public:

// Adds a word into the data structure.
void addWord(string word) {
insert(word);
}

// Returns if the word is in the data structure. A word could
// contain the dot character '.' to represent any one letter.
bool search(string word) {
TrieNode *r = root;
int depth = 0;
bool result = traverse(r, word, depth);
return result;
}
WordDictionary() {
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 search1(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();
}
bool traverse(TrieNode *r, string key, int depth)
{
//深度优先遍历
char s = key[depth];
int index = 0;
bool result = false;
TrieNode *current = NULL;
if (depth == (key.length() - 1))
{
//退出条件 这是遍历到key的最后一个元素了
if (s == '.')
{
for (int i = 0; i < 26; i++)
{
index = i;
current = r->get(index);
if (current&&current->geted())
return true;
}
return false;
}
else
{
index = s - 'a';
current = r->get(index);
if (current&&current->geted())
return true;
return false;
}
}
else
{
if (s == '.')
{
result = false;
for (int i = 0; i < 26; i++)
{
index = i;
current = r->get(index);
if (!current)
continue; //如果这个地方没有节点,就回朔
result = result || traverse(current, key, depth + 1);
//一旦一个匹配成功,后面的就不用考虑了
if (result)
break;
}
return result;
}
else
{
index = s - 'a';
current = r->get(index);
if (!current)
return false;
result = traverse(current, key, depth + 1);
return result;
}
}


}
// 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;
}
};

// Your WordDictionary object will be instantiated and called as such:
// WordDictionary wordDictionary;
// wordDictionary.addWord("word");
// wordDictionary.search("pattern");



  评论这张
 
阅读(5)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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