原题描述
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.
Trie+回溯算法
本题为了实现方便采用静态分配法，详细的Trie树可以见我的另一篇博客，回溯可以参考博客
C++代码
typedef struct trie_node {
bool valid;
struct trie_node* next[26];
}TrieNode, *Trie;
TrieNode* createTrieNode() {
TrieNode* node = (TrieNode*)malloc(sizeof(TrieNode));
node->valid = false;
memset(node->next, NULL, sizeof(node->next));
return node;
}
class WordDictionary {
public:
Trie root = createTrieNode();
// Adds a word into the data structure.
void addWord(string word) {
if (word.length() <= 0) {
return;
}
int len = word.length();
TrieNode* p = root;
for (int i = 0; i < len; i++) {
if (p->next[word[i] - 'a'] == NULL) {
p->next[word[i] - 'a'] = createTrieNode();
}
p = p->next[word[i] - 'a'];
}
p->valid = true;
}
// 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) {
if (word.length() <= 0) {
return false;
}
int len = word.length();
TrieNode* p = root;
for (int i = 0; i < len; i++) {
if (word[i] != '.') {
if (p->next[word[i] - 'a'] == NULL) {
return false;
}
else {
p = p->next[word[i] - 'a'];
}
}
else {
return backTrace(p, word, i);
}
}
return p->valid;
}
bool backTrace(Trie p, string word, int depth) {
int len = word.length();
if (len <= 0) {
return true;
}
TrieNode* p_save;
for (int j = 0; j < 26; j++) {
if (p->next[j] != NULL) {
p_save = p;
p = p->next[j];
bool check = true;
for (int i = depth+1; i < len; i++) {
if (word[i] != '.') {
if (p->next[word[i] - 'a'] == NULL) {
check = false;
break;
}
else {
p = p->next[word[i] - 'a'];
}
}
else {
if (backTrace(p, word, i)) {
return true;
}
else {
check = false;
break;
}
}
}
if (check && p->valid) {
return true;
}
else {
p = p_save;
}
}
}
return false;
}
};
// Your WordDictionary object will be instantiated and called as such:
// WordDictionary wordDictionary;
// wordDictionary.addWord("word");
// wordDictionary.search("pattern");