|
| 1 | +# Trie（发音类似 "try"）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼 |
| 2 | +# 写检查。 |
| 3 | +# |
| 4 | +# 请你实现 Trie 类： |
| 5 | +# |
| 6 | +# |
| 7 | +# Trie() 初始化前缀树对象。 |
| 8 | +# void insert(String word) 向前缀树中插入字符串 word 。 |
| 9 | +# boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false |
| 10 | +# 。 |
| 11 | +# boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否 |
| 12 | +# 则，返回 false 。 |
| 13 | +# |
| 14 | +# |
| 15 | +# |
| 16 | +# |
| 17 | +# 示例： |
| 18 | +# |
| 19 | +# |
| 20 | +# 输入 |
| 21 | +# ["Trie", "insert", "search", "search", "startsWith", "insert", "search"] |
| 22 | +# [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]] |
| 23 | +# 输出 |
| 24 | +# [null, null, true, false, true, null, true] |
| 25 | +# |
| 26 | +# 解释 |
| 27 | +# Trie trie = new Trie(); |
| 28 | +# trie.insert("apple"); |
| 29 | +# trie.search("apple"); // 返回 True |
| 30 | +# trie.search("app"); // 返回 False |
| 31 | +# trie.startsWith("app"); // 返回 True |
| 32 | +# trie.insert("app"); |
| 33 | +# trie.search("app"); // 返回 True |
| 34 | +# |
| 35 | +# |
| 36 | +# |
| 37 | +# |
| 38 | +# 提示： |
| 39 | +# |
| 40 | +# |
| 41 | +# 1 <= word.length, prefix.length <= 2000 |
| 42 | +# word 和 prefix 仅由小写英文字母组成 |
| 43 | +# insert、search 和 startsWith 调用次数 总计 不超过 3 * 104 次 |
| 44 | +# |
| 45 | +# Related Topics 设计 字典树 哈希表 字符串 |
| 46 | +# 👍 1255 👎 0 |
| 47 | + |
| 48 | + |
| 49 | +# leetcode submit region begin(Prohibit modification and deletion) |
| 50 | +classTreeNode(object): |
| 51 | +def__init__(self,char=None): |
| 52 | +self.char=char |
| 53 | +self.is_end=False |
| 54 | +self.children= {} |
| 55 | + |
| 56 | +definsert(self,c): |
| 57 | +ifcinself.children: |
| 58 | +returnself.children[c] |
| 59 | +else: |
| 60 | +self.children[c]=TreeNode(c) |
| 61 | +returnself.children[c] |
| 62 | + |
| 63 | +defsearch(self,c): |
| 64 | +returnself.children.get(c,None) |
| 65 | +classTrie: |
| 66 | + |
| 67 | +def__init__(self): |
| 68 | +self.root=TreeNode() |
| 69 | + |
| 70 | +definsert(self,word:str)->None: |
| 71 | +node=self.root |
| 72 | +forcinword: |
| 73 | +node=node.insert(c) |
| 74 | +node.is_end=True |
| 75 | + |
| 76 | +defsearch(self,word:str)->bool: |
| 77 | +node=self.root |
| 78 | +forcinword: |
| 79 | +node=node.search(c) |
| 80 | +ifnotnode: |
| 81 | +returnFalse |
| 82 | +ifnode.is_end: |
| 83 | +returnTrue |
| 84 | +else: |
| 85 | +returnFalse |
| 86 | + |
| 87 | +defstartsWith(self,prefix:str)->bool: |
| 88 | +node=self.root |
| 89 | +forcinprefix: |
| 90 | +node=node.search(c) |
| 91 | +ifnotnode: |
| 92 | +returnFalse |
| 93 | +returnTrue |
| 94 | + |
| 95 | + |
| 96 | +# Your Trie object will be instantiated and called as such: |
| 97 | +# obj = Trie() |
| 98 | +# obj.insert(word) |
| 99 | +# param_2 = obj.search(word) |
| 100 | +# param_3 = obj.startsWith(prefix) |
| 101 | +# leetcode submit region end(Prohibit modification and deletion) |