# [LeetCode] 211. Add and Search Word - Data structure design 添加和查找单词-数据结构设计

2021年09月15日 阅读数：3

Design a data structure that supports the following two operations:html

```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.java

Example:node

```addWord("bad")
search("b..") -> true
```

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

208. Implement Trie (Prefix Tree) 的拓展，字典树的数据结构设计应用。express

Java: Using backtrack to check each character of word to search.数据结构

```public class WordDictionary {
public class TrieNode {
public TrieNode[] children = new TrieNode[26];
public String item = "";
}

private TrieNode root = new TrieNode();

TrieNode node = root;
for (char c : word.toCharArray()) {
if (node.children[c - 'a'] == null) {
node.children[c - 'a'] = new TrieNode();
}
node = node.children[c - 'a'];
}
node.item = word;
}

public boolean search(String word) {
return match(word.toCharArray(), 0, root);
}

private boolean match(char[] chs, int k, TrieNode node) {
if (k == chs.length) return !node.item.equals("");
if (chs[k] != '.') {
return node.children[chs[k] - 'a'] != null && match(chs, k + 1, node.children[chs[k] - 'a']);
} else {
for (int i = 0; i < node.children.length; i++) {
if (node.children[i] != null) {
if (match(chs, k + 1, node.children[i])) {
return true;
}
}
}
}
return false;
}
}　　```

Python:post

```class TrieNode:
# Initialize your data structure here.
def __init__(self):
self.is_string = False
self.leaves = {}

class WordDictionary:
def __init__(self):
self.root = TrieNode()

# @param {string} word
# @return {void}
# Adds a word into the data structure.
curr = self.root
for c in word:
if c not in curr.leaves:
curr.leaves[c] = TrieNode()
curr = curr.leaves[c]
curr.is_string = True

# @param {string} word
# @return {boolean}
# Returns if the word is in the data structure. A word could
# contain the dot character '.' to represent any one letter.
def search(self, word):
return self.searchHelper(word, 0, self.root)

def searchHelper(self, word, start, curr):
if start == len(word):
return curr.is_string
if word[start] in curr.leaves:
return self.searchHelper(word, start+1, curr.leaves[word[start]])
elif word[start] == '.':
for c in curr.leaves:
if self.searchHelper(word, start+1, curr.leaves[c]):
return True

return False　　```

C++:url

```class WordDictionary {
public:
struct TrieNode {
public:
TrieNode *child[26];
bool isWord;
TrieNode() : isWord(false) {
for (auto &a : child) a = NULL;
}
};

WordDictionary() {
root = new TrieNode();
}

// Adds a word into the data structure.
TrieNode *p = root;
for (auto &a : word) {
int i = a - 'a';
if (!p->child[i]) p->child[i] = new TrieNode();
p = p->child[i];
}
p->isWord = 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) {
return searchWord(word, root, 0);
}

bool searchWord(string &word, TrieNode *p, int i) {
if (i == word.size()) return p->isWord;
if (word[i] == '.') {
for (auto &a : p->child) {
if (a && searchWord(word, a, i + 1)) return true;
}
return false;
} else {
return p->child[word[i] - 'a'] && searchWord(word, p->child[word[i] - 'a'], i + 1);
}
}

private:
TrieNode *root;
};
```

相似题目：设计