Trie Class Data Structure in Python

  • 时间:2020-09-09 13:16:32
  • 分类:网络文摘
  • 阅读:147 次

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 true
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 true

Note:
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 Trie Class Data Structure in Python data structure python

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) —

推荐阅读:
做一个有道德的人|小学作文  写人作文我们班的xx作文  描写校园春景的作文  后勤的一天  失败中的成功作文500字  开了芙蓉,醉了石榴  最美的永远是母亲  捶背作文150字  蹇叔哭师原文及翻译  百家讲坛系列节目《易中天品三国》MP3蓝奏云下载 
评论列表
添加评论