> For the complete documentation index, see [llms.txt](https://quenluo.gitbook.io/leecode-python/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://quenluo.gitbook.io/leecode-python/211.-add-and-search-word-data-structure-design.md).

# 211. Add and Search Word - Data structure design

## Question 211

[https://leetcode.com/problems/add-and-search-word-data-structure-design](https://leetcode.com/problems/add-and-search-word-data-structure-design/submissions/1)

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.

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

## Answer

### v1.use defaultdict （98.83%）

1. 建立一個 collections class 中的 defaultdict() ，命名為 word\_store
2. \[addWord] --> 依據字串長度來分 list 存：\
   \[ ( 2,  \["ab", "dv"] ),  ( 1,  \["a","b","c"] ),  ( 6, \[ "asdfgh"] ) ]
3. \[search] --> 

   a) 如果該 search 字串沒有 “.” ，直接找 word\_store 中該長度的字串有沒有符合的\
   b) 如果有 “.”，一個字母一個字母去比對該長度 list 中的字詞

```python
class WordDictionary(object):
    def __init__(self):
         # Initialize a collection to store words
        self.word_store = collections.defaultdict(list)
    
    
    def addWord(self, word):
        # Adds a word into word_store
        # Classified by how long is the word
        self.word_store[len(word)].append(word)
    
    
    def search(self, word):

        word_len = len(word)
        if '.' not in word:
            return word in self.word_store[len(word)]
        else:
            for item in self.word_store[word_len]:
                # Comparison character one by one
                for alpha in range(0,word_len):
                    if word[alpha] != "." and word[alpha] != item[alpha]:
                        break
                    if alpha == (word_len-1) :
                        return True
    
            return False
```