###### tags: `Leetcode` `medium` `design` `hash` `python` `c++`

# 211. Design Add and Search Words Data Structure

## [題目連結:] https://leetcode.com/problems/design-add-and-search-words-data-structure/

## 題目:
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

## 解題想法:
* 同概念題目: [208. Implement Trie (Prefix Tree)](/RFOtQ4WeRXiUxREkhkCKBA)

* 實作字典樹(前綴樹)
* 額外條件: **' . '** 能做為任何字母
* 字典樹的每一個node皆是map:
* key: 當前字母
* val: map，所有與當前字母有關聯的下個字母
* **若當前字母為某單詞的結尾，則在其val中新增一個key為"#"**

## Python:

#類似P208
class WordDictionary(object):

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

    def addWord(self, word):
        """
        :type word: str
        :rtype: None
        """
        curMap = self.root
        for char in word:
            if char not in curMap:
                curMap[char]={}
            curMap=curMap[char]
        #當為單詞尾加上個'#'
        curMap['#']=True
        

    def search(self, word):
        """
        :type word: str
        :rtype: bool
        """
        return self.dfs(self.root,word,pos=0)
    
    def dfs(self,curMap,word,pos):
        if pos==len(word):
            return True if '#' in curMap else False  #若有'#'才表示為一個完整單詞
        #當遇到萬用'.'時 往後拜訪其他正常char
        elif word[pos]=='.':
            for child in curMap:
                #不能是'#' 才能往下遍歷正常的char
                if child!='#' and self.dfs(curMap[child],word,pos+1):
                    return True
            return False
        elif word[pos] not in curMap:
            return False
        else:
            #正常往後拜訪
            return self.dfs(curMap[word[pos]],word,pos+1)


# Your WordDictionary object will be instantiated and called as such:
# obj = WordDictionary()
# obj.addWord(word)
# param_2 = obj.search(word)

res = WordDictionary()
res.addWord("bad")
res.addWord("dad")
res.addWord("mad")
print(res.search("pad"))
print(res.search("bad"))
print(res.search(".ad"))

## C++:

#include<bits/stdc++.h>
using namespace std;

class TrieNode{
public:
    TrieNode* childMap[26];
    bool wordEnd;
    TrieNode(): wordEnd(false){
        for (auto& child: childMap) child=nullptr;
    }
};

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

    void addWord(string word) {
        TrieNode* curMap=root;
        for (char val: word){
            int num=val-'a';
            if (!curMap->childMap[num])
                curMap->childMap[num]=new TrieNode();
            curMap=curMap->childMap[num];
        }
        curMap->wordEnd=true;
    }

    bool search(string word) {
        return dfs(root,word,0);
    }

    //string call by reference '&'
    bool dfs(TrieNode* curMap, string& word, int pos){
        if (pos==word.size())
            return curMap->wordEnd;
        else if (word[pos]=='.'){
            for (auto& child: curMap->childMap){
                if (child && dfs(child, word, pos+1))
                    return true;
            }
            return false;
        }
        else if (!curMap->childMap[word[pos]-'a'])
            return false;
        else
            return dfs(curMap->childMap[word[pos]-'a'],word,pos+1);
    }
private:
   TrieNode* root;
};

int main(){
    WordDictionary* res=new WordDictionary();
    res->addWord("bad");
    res->addWord("dad");
    res->addWord("mad");
    bool ans1=res->search("pad"); //0
    bool ans2=res->search("bad"); //1
    bool ans3=res->search(".ad"); //1
    cout<<ans1<<" "<<ans2<<" "<<ans3<<endl;
    return 0;
}