Trie Class Data Structure in Python
- 时间:2020-09-09 13:16:32
- 分类:网络文摘
- 阅读:94 次
Implement a trie with insert, search, and startsWith methods.
Example:
1 2 3 4 5 6 7 Trie trie = new Trie(); trie.insert("apple"); trie.search("apple"); // returns true trie.search("app"); // returns false trie.startsWith("app"); // returns true trie.insert("app"); trie.search("app"); // returns trueTrie trie = new Trie(); trie.insert("apple"); trie.search("apple"); // returns true trie.search("app"); // returns false trie.startsWith("app"); // returns true trie.insert("app"); trie.search("app"); // returns trueNote:
You may assume that all inputs are consist of lowercase letters a-z.
All inputs are guaranteed to be non-empty strings.Your Trie object will be instantiated and called as such:
1 2 3 4 obj = Trie() obj.insert(word) param_2 = obj.search(word) param_3 = obj.startsWith(prefix)obj = Trie() obj.insert(word) param_2 = obj.search(word) param_3 = obj.startsWith(prefix)
Implement a Trie in Python
The Trie is a useful data structure that can be used to store words so that we can check if any given word (or prefix) is in the list in linear time O(N).

trie-example
It is simple to implement a Trie class in Python. For each Trie Node, we need to tell if is a leaf node (indicates a word), and the children nodes. Then we start from the begining of the word, follow the path in the Trie tree, until the end, or the corresponding child is not existent in the Trie.
The startsWith, search and insert are of similar implementations with slight difference.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 | class Trie(object): def __init__(self): """ Initialize your data structure here. """ self.nodes = {} self.leaf = False def insert(self, word): """ Inserts a word into the trie. :type word: str :rtype: None """ root = self for i in word: if i in root.nodes: root = root.nodes[i] else: root.nodes[i] = Trie() root = root.nodes[i] root.leaf = True def search(self, word): """ Returns if the word is in the trie. :type word: str :rtype: bool """ root = self for i in word: if i in root.nodes: root = root.nodes[i] else: return False return root.leaf def startsWith(self, prefix): """ Returns if there is any word in the trie that starts with the given prefix. :type prefix: str :rtype: bool """ root = self for i in prefix: if i in root.nodes: root = root.nodes[i] else: return False return True |
class Trie(object): def __init__(self): """ Initialize your data structure here. """ self.nodes = {} self.leaf = False def insert(self, word): """ Inserts a word into the trie. :type word: str :rtype: None """ root = self for i in word: if i in root.nodes: root = root.nodes[i] else: root.nodes[i] = Trie() root = root.nodes[i] root.leaf = True def search(self, word): """ Returns if the word is in the trie. :type word: str :rtype: bool """ root = self for i in word: if i in root.nodes: root = root.nodes[i] else: return False return root.leaf def startsWith(self, prefix): """ Returns if there is any word in the trie that starts with the given prefix. :type prefix: str :rtype: bool """ root = self for i in prefix: if i in root.nodes: root = root.nodes[i] else: return False return True
The space requirement for Trie is O(NM) where N is the number of words, and M is the average length of each word. The runtime complexity for searching a word in the Trie is O(M).
The C++ Implementation of Trie can be found here: The Beginners’ Guide to Trie: How to Use the Trie in C++?
–EOF (The Ultimate Computing & Technology Blog) —
推荐阅读:四舍五入法怎么用 多边形的内角和公式 梯形上底的定义是什么 用放大镜看角变大了吗 四位一级和三位分节 求近似数的方法有哪几种 自然数的产生 有没有平方十米 二进制和十六进制 献礼教师节作文
- 评论列表
-
- 添加评论