# Leetcode 211. Design Add and Search Words Data Structure

## 題解

### Recursive

class TrieNode:
    def __init__(self):
        self.end = False
        self.map = {}

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

    def addWord(self, word: str) -> None:
        cur = self.head
        for s in word:
            if s not in cur.map:
                cur.map[s] = TrieNode()
            cur = cur.map[s]
        cur.end = True

    def search(self, word: str) -> bool:
        return self.traversal(self.head,0,word)

    def traversal(self,cur: TrieNode, i: int,word: str):
        n = len(word)
        while i < n and cur and len(cur.map) > 0:
            s = word[i]
            if s == ".":
                for key,value in enumerate(cur.map):
                    if self.traversal(cur.map[value],i+1,word):
                        return True
                else:
                    return False
            elif s in cur.map:
                cur = cur.map[s]
            else:
                return False
            i += 1
        return cur.end and i == n

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