# Leetcode 211 Add and Search Word - Data structure design

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")
search("b..") -> true```

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

```class node
{
public:
int flag;
node* next[26];
node(int x = 0)
{
flag = x;
memset(next, 0, sizeof(next));
}
};
class WordDictionary {
public:
node* root;
/** Initialize your data structure here. */
WordDictionary() {
root = new node();
}
/** Adds a word into the data structure. */
node* p = root;
for(int i = 0; i < word.size(); i++)
{
if(!p->next[word[i] - 'a']) p->next[word[i] - 'a'] = new node();
p = p->next[word[i] - 'a'];
}
p->flag = 1;
}
/** 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) {
return dfs(word, root);
}
bool dfs(string word, node* now)
{
if(word.size() == 0)
{
if(now->flag) return true;
return false;
}
if(word[0]!='.')
{
if(!now->next[word[0] - 'a']) return false;
return dfs(word.substr(1), now->next[word[0]-'a']);
}
else
for(int i = 0; i < 26; i++) if(now->next[i] && dfs(word.substr(1), now->next[i])) return true;
return false;
}
};
/**
* Your WordDictionary object will be instantiated and called as such:
* WordDictionary obj = new WordDictionary();
* bool param_2 = obj.search(word);
*/```

0 条评论

• ### Leetcode 208 Implement Trie (Prefix Tree) 字典树

Implement a trie with insert, search, and startsWith methods. Note: You may ...

• ### Leetcode 79 Word Search

Given a 2D board and a word, find if the word exists in the grid. The word can...

• ### Leetcode 120 Triangle

Given a triangle, find the minimum path sum from top to bottom. Each step you m...

• ### [文本语义相似] 基于bow的余弦距离

文本相似在问答系统中有很重要的应用，如基于知识的问答系统（Knowledge-based QA），基于文档的问答系统（Documen-based QA），以及基...

• ### php转换上传word文件为PDF的方法【基于COM组件】

本文实例讲述了php转换上传word文件为PDF的方法。分享给大家供大家参考，具体如下：

• ### leetcode-824-Goat Latin（字符串的处理）

A sentence S is given, composed of words separated by spaces. Each word consists...