<!--
 * @Description: 
 * @Autor: Au3C2
 * @Date: 2021-04-14 12:50:01
 * @LastEditors: Au3C2
 * @LastEditTime: 2021-04-14 13:01:49
-->
```python
class Trie:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.trie = dict()


    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        self.buildTrie(word+'#',self.trie)


    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        return self.startsWith(word+'#')


    def startsWith(self, prefix: str) -> bool:
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        return self.dfsSearch(prefix,self.trie)

    def dfsSearch(self,prefix,d):
        if not prefix:
            return True
        return prefix[0] in d and self.dfsSearch(prefix[1:],d[prefix[0]])

    def buildTrie(self,word,d):
        if not word: 
            return
        if d == None:
            d = dict()
        if word[0] not in d:
            d[word[0]] = dict()
        d[word[0]] = self.buildTrie(word[1:],d[word[0]])  
        return d


# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)
```
字典树 中等 每日一题 👆我的字典树用的是递归生成和查找

https://leetcode-cn.com/submissions/detail/167683603/

👇字典树循环查找写法，时间少一半，空间省好多
```python
class Trie:

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

    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        tmp=self.tree

        for ch in list(word):
            if not ch in tmp:
                tmp[ch]={} 
            tmp=tmp[ch]

        tmp['#']="#"           


    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """

        tmp=self.tree

        for ch in list(word):
            if ch in tmp:
                tmp=tmp[ch]
            else:
                return False 

        if "#" in tmp:
            return True
        else:
            return False           


    def startsWith(self, prefix: str) -> bool:
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        tmp=self.tree

        for ch in list(prefix):
            if ch in tmp:
                tmp=tmp[ch]
            else:
                return False 
        return True 


# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)
```