# LeetCode- Add and Search Word – Data structure design Solution

leetcode 211 Trie的添加及搜索

Design a data structure that supports adding new words and finding if a string matches any previously added string.

Implement the `WordDictionary` class:

• `WordDictionary()` Initializes the object.
• `void addWord(word)` Adds `word` to the data structure, it can be matched later.
• `bool search(word)` Returns `true` if there is any string in the data structure that matches `word` or `false` otherwise. `word` may contain dots `'.'` where dots can be matched with any letter.

Example:

Input

```["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
```

Output

```[null,null,null,null,false,true,true,true]

```

Explanation

```WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad"); // return False
wordDictionary.search("bad"); // return True
wordDictionary.search(".ad"); // return True
wordDictionary.search("b.."); // return True
```

Constraints:

• `1 <= word.length <= 500`
• `word` in `addWord` consists lower-case English letters.
• `word` in `search` consist of  `'.'` or lower-case English letters.
• At most `50000` calls will be made to `addWord` and `search`.

Hide Hint #1

You should be familiar with how a Trie works. If not, please work on this problem: Implement Trie (Prefix Tree) first.

#### 使用HashMap

java

```class WordDictionary {

// 定义一个hashset，存放root
//private Set< String> dict;
private final Map< Integer, Set<String>> dict;

/** Initialize your data structure here. */
public WordDictionary() {
dict = new HashMap<>();
}

public void addWord(String word) {

int n = word.length();
//dict.add(word);
dict.computeIfAbsent(n, f->new HashSet<>()).add(word);
return ;
}

public boolean search(String word) {

int n = word.length();

if( dict.containsKey(n) == false) {
return false;
}

for (String s: dict.get(n)) {
int i=0;
while (i<n && (s.charAt(i) == word.charAt(i) || word.charAt(i)=='.') )
i++;
if (i==n ){
return true;
}
}
return false;
}
}```

#### 使用Trie树

```class TrieNode {
char c;
HashMap<Character, TrieNode> children = new HashMap<Character, TrieNode>();
boolean isLeaf;
public TrieNode() {}
public TrieNode(char c){
this.c = c;
}
}

class WordDictionary {

private  TrieNode root;

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

public void addWord(String word) {

HashMap<Character, TrieNode> children = root.children;

for(int i =0; i<word.length();i++){
char c = word.charAt(i);

TrieNode t = null;
if (children.containsKey(c)){
t = children.get(c);
} else {
t = new TrieNode(c);
children.put(c,t);
}

children = t.children;

if (i == word.length()-1){
t.isLeaf = true;
}

}
}
public boolean search(String word) {
return dfsSearch(root.children, word, 0);
}

public boolean dfsSearch(HashMap<Character, TrieNode>children, String word, int start) {
if (start == word.length()){
if (children.size() == 0){
return true;
}
else {
return false;
}
}
char c = word.charAt(start);
// 字母
if( children.containsKey(c) ) {
// 查询单词长度相等且非前缀
if (start == word.length()-1 && children.get(c).isLeaf)   {
return true;
}
// 继续查找
return dfsSearch(children.get(c).children, word, start+1);
//通配符
} else if (c == '.'){
boolean result = false;
for (Map.Entry<Character, TrieNode >child: children.entrySet()){
if (start == word.length()-1 && child.getValue().isLeaf){
return true;
}
if (dfsSearch(child.getValue().children, word, start+1)){
result = true;
}
}
return result;

}else {
return false;
}
}

}```

#### Python语言一些实现

1）使用字典方式构造

```class WordDictionary:

def __init__(self):
"""
Initialize your data structure here.
"""
self.root ={}

def addWord(self, word: str) -> None:
node = self.root
for char in word:
node = node.setdefault(char, {})
node[None] = None

def search(self, word: str) -> bool:
def find(word, node):
if not word:
return None in node
char, word = word[0], word[1:]
if char != '.':
return char in node and find(word,node[char])
return any(find(word,kid) for  kid in node.values() if kid)
return find(word, self.root)```

`root = {'b':{'i':{'g':{None, None}}, 'a':{'d':{None, None}}}, 'c':{None:None}}`

find的实现可以表示为

```def find(word, node):
if not word:
return None in node
char, word = word[0], word[1:]
if char != '.':
return char in node and find(word, node[char])

li = []
for kid in node.values():
if kid:
li.append( find(word, kid))

if not li:
return None in node
re = False
for kid in li:
re = re or kid
return re```

2）在看一下StefanPochmann 写的另外一个实现

```class WordDictionary:

def __init__(self):
self.root = {}

def addWord(self, word):
node = self.root
for char in word:
node = node.setdefault(char, {})
node['\$'] = None

def search(self, word):
nodes = [self.root]
for char in word + '\$':
nodes = [kid for node in nodes for kid in
([node[char]] if char in node else
filter(None, node.values()) if char == '.' else [])]
return bool(nodes)```

How to Write a Nested For Loop in One Line Python?

```class WordDictionary:

def __init__(self):
self.root = {}

def addWord(self, word):
node = self.root
for char in word:
node = node.setdefault(char, {})
node['\$'] = None

def search(self, word):
nodes = [self.root]

for char in word + '\$':
# node 是字典结构 dict
kid=[]
for node in nodes:
li=[]
if char in node:
li = [node[char]]
else:
# 当前节点下所有的值
if char == '.':
li = filter(None, node.values())
else:
li = []
kid.extend(li)
nodes=[]
nodes.extend(kid)
#            nodes = copy.deepcopy(kid)
#print(nodes)

return bool(nodes)
```

#### 参考及引用：

LeetCode – Add and Search Word – Data structure design (Java)

https://leetcode.com/explore/learn/card/trie/148/practical-application-i/1052/discuss/59576/Tree-solutions-18-20-lines

https://leetcode.com/explore/learn/card/trie/148/practical-application-i/1052/discuss/59576/Tree-solutions-18-20-lines

Photo by  Jη ✿@Jeanne_8L from twitter

Comments are closed.