# LeetCode-  Add and Search Word - Data structure design  Solution
Date: 2021-01-27


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)](https://leetcode.com/problems/implement-trie-prefix-tree/) first.

 

#### **使用HashMap**

* * *

开始想法是使用Set方式但是在单词初始时，由于同时需要比较单词长度和内容，出现limit time， 后来在讨论区找到以下方案， 将单词的长度做为key， 长度相同再比较内容：

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)
```

这个版本python实现，使用了字典做为子节点类似下面这种结构：

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

找到None认为找到单词， 遇到通配符'.' ， 以前是一个分支的递归查找， 改为多个分支递归查找 ， kid in node.values(), 只要有一个满足要求即可反馈成功， 也就是any的作用

2）在看一下[StefanPochmann](https://leetcode.com/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)
```

 

具体思路和上面一样子只是写得更简洁一些， one-lines, 感觉这种不太适合我这样的初学者， 看得有点头疼

直到这个贴子才有些理解。  这篇文章作者还专门出了一本  [Python One-Liners](https://amzn.to/2WAYeJE)  的书。

https://blog.finxter.com/how-to-write-a-nested-for-loop-in-one-line-python/

针对search拆解如下

```
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)

```

这里的结束符号由None改了'$',  使用None通过char 是无法遍历的。

#### 参考及引用：

* * *

[LeetCode – Add and Search Word – Data structure design (Java)](https://www.programcreek.com/2014/05/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)

[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