跳转至

字典树#
发布于2020-12-30
上次编辑2021-04-19

Python 用哈希表实现的效率比较高，C++ 用数组实现的效率比较高。

Python
 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
class Trie:
    def __init__(self):
        self.root = {}

    def insert(self, word: str) -> None:
        p = self.root
        for c in word:
            if c not in p:
                p[c] = {}
            p = p[c]
        p["$"] = ""

    def search(self, word: str) -> bool:
        p = self.root
        for c in word:
            if c not in p:
                return False
            p = p[c]
        return "$" in p

    def startswith(self, prefix: str) -> bool:
        p = self.root
        for c in prefix:
            if c not in p:
                return False
            p = p[c]
        return True
C++
 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
struct TrieNode {
    unordered_map<char, TrieNode*> children;
    bool is_word;
};

class Trie {
public:
    TrieNode *root;

    Trie() {
        root = new TrieNode();
    }

    void insert(string word) {
        auto p = root;
        for (auto &c : word) {
            p = p->children[c] ? p->children[c] : (p->children[c] = new TrieNode());
        }
        p->is_word = true;
    }

    bool search(string word) {
        auto p = root;
        for (auto &c : word) {
            if (p->children.find(c) == p->children.end()) {
                return false;
            }
            p = p->children[c];
        }
        return p->is_word;
    }

    bool startsWith(string prefix) {
        auto p = root;
        for (auto &c : prefix) {
            if (p->children.find(c) == p->children.end()) {
                return false;
            }
            p = p->children[c];
        }
        return true;
    }
};
Python
 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
class TrieNode:
    def __init__(self):
        self.children = [None] * 26
        self.is_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        p = self.root
        for c in word:
            i = ord(c) - 97
            if not p.children[i]:
                p.children[i] = TrieNode()
            p = p.children[i]
        p.is_word = True

    def search(self, word: str) -> bool:
        p = self.root
        for c in word:
            i = ord(c) - 97
            if not p.children[i]:
                return False
            p = p.children[i]
        return p.is_word

    def startswith(self, prefix: str) -> bool:
        p = self.root
        for c in prefix:
            i = ord(c) - 97
            if not p.children[i]:
                return False
            p = p.children[i]
        return True
C++
 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
struct TrieNode {
    TrieNode *children[26];
    bool is_word;
};

class Trie {
public:
    TrieNode *root;

    Trie() {
        root = new TrieNode();
    }

    void insert(string word) {
        auto p = root;
        for (auto &c : word) {
            p = p->children[c - 'a'] ? p->children[c - 'a'] : (p->children[c - 'a'] = new TrieNode());
        }
        p->is_word = true;
    }

    bool search(string word) {
        auto p = root;
        for (auto &c : word) {
            if (!p->children[c - 'a']) {
                return false;
            }
            p = p->children[c - 'a'];
        }
        return p->is_word;
    }

    bool startsWith(string prefix) {
        auto p = root;
        for (auto &c : prefix) {
            if (!p->children[c - 'a']) {
                return false;
            }
            p = p->children[c - 'a'];
        }
        return true;
    }
};

例题#

  1. https://en.wikipedia.org/wiki/Trie ↩

  2. https://oi-wiki.org/string/trie/ ↩

返回顶部

在手机上阅读