Code & Func

第51天。

Implement a trie with insert, search, and startsWith methods.

Note: You may assume that all inputs are consist of lowercase letters a-z.

Tire也就是前缀树，也叫字典树。

它大概是是这样子的：

除了root节点以外，每个节点都有一个字符。
从根节点到**某个节点（可以不是叶子节点）**的一条路径表示一个字符串。
对于某个节点其孩子节点的字符不唯一

每个节点都可以唯一对应一个字符串，即使每个节点只存放一个字符，但是root节点到这个节点的路径可以唯一确定一个字符串。

既然说它是前缀树，那肯定和前缀有关啦。两个节点所代表的字符串用公共前缀，那么root节点到他们的路径肯定有公共路径。

1
class TrieNode:
2

3
        def __init__(self):
4
            """
5
            Initialize the TireNode.
6
            """
7
            self.child = {}
8
            self.count = 0
9

10
class Trie:
11

12
    def __init__(self):
13
        """
14
        Initialize your data structure here.
15
        """
53 collapsed lines
16
        self.root = TrieNode()
17

18

19
    def insert(self, word):
20
        """
21
        Inserts a word into the trie.
22
        :type word: str
23
        :rtype: void
24
        """
25
        p = self.root
26
        for c in word:
27
            q = p.child.get(c,None)
28
            if q is None:
29
                p.child[c] = TrieNode()
30
                q = p.child[c]
31
            p = q
32
        p.count += 1
33

34
    def search(self, word):
35
        """
36
        Returns if the word is in the trie.
37
        :type word: str
38
        :rtype: bool
39
        """
40
        p = self.root
41
        for c in word:
42
            q = p.child.get(c,None)
43
            if q is None:
44
                return False
45
            p = q
46
        return p.count > 0
47

48

49
    def startsWith(self, prefix):
50
        """
51
        Returns if there is any word in the trie that starts with the given prefix.
52
        :type prefix: str
53
        :rtype: bool
54
        """
55
        p = self.root
56
        for c in prefix:
57
            q = p.child.get(c,None)
58
            if q is None:
59
                return False
60
            p = q
61
        return True
62

63

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

因为python中有一些好用的数据结构，比如说dict，所以实现起来并不难。

贴一个dicuss中的c++解法吧，因为他这里限定了字符只是26个，所以写起来也挺方便的：

1
class TrieNode
2
{
3
public:
4
    TrieNode *next[26];
5
    bool is_word;
6

7
    // Initialize your data structure here.
8
    TrieNode(bool b = false)
9
    {
10
        memset(next, 0, sizeof(next));
11
        is_word = b;
12
    }
13
};
14

15
class Trie
44 collapsed lines
16
{
17
    TrieNode *root;
18
public:
19
    Trie()
20
    {
21
        root = new TrieNode();
22
    }
23

24
    // Inserts a word into the trie.
25
    void insert(string s)
26
    {
27
        TrieNode *p = root;
28
        for(int i = 0; i < s.size(); ++ i)
29
        {
30
            if(p -> next[s[i] - 'a'] == NULL)
31
                p -> next[s[i] - 'a'] = new TrieNode();
32
            p = p -> next[s[i] - 'a'];
33
        }
34
        p -> is_word = true;
35
    }
36

37
    // Returns if the word is in the trie.
38
    bool search(string key)
39
    {
40
        TrieNode *p = find(key);
41
        return p != NULL && p -> is_word;
42
    }
43

44
    // Returns if there is any word in the trie
45
    // that starts with the given prefix.
46
    bool startsWith(string prefix)
47
    {
48
        return find(prefix) != NULL;
49
    }
50

51
private:
52
    TrieNode* find(string key)
53
    {
54
        TrieNode *p = root;
55
        for(int i = 0; i < key.size() && p != NULL; ++ i)
56
            p = p -> next[key[i] - 'a'];
57
        return p;
58
    }
59
};