LeetCode 208 实现 Trie (前缀树)

LeetCode 208 实现 Trie (前缀树)

实现一个前缀树,包括 insert, search, 和 startsWith 三个操作。

Trie前缀树是一种树形数据结构,用于检索字符串数据集中的键,常用于自然语言处理的Query Completion。Trie对比于Hash的优势在于,Hash冲突会随着Hash的增加而增加,其搜索时间复杂度在最坏情况下可能为O(n),其中n是key的数量,而trie的时间复杂度仅为O(m),其中m是key的最大长度,并且Trie可以使用比Hash更少的空间。而在平衡树中搜索的时间复杂度为O(mlogn)。

// C++
class Trie {
    struct TrieNode {
        vector<TrieNode *> next;
        bool is_end;

        TrieNode() : next(vector<TrieNode *>(26, nullptr)), is_end(false) {}
    };

    TrieNode *root;
public:
    Trie() {
        root = new TrieNode();
    }

    void insert(string word) {
        auto node = root;
        for (auto c:word) {
            if (!node->next[c - 'a'])
                node->next[c - 'a'] = new TrieNode();
            node = node->next[c - 'a'];
        }
        node->is_end = true;
    }

    bool search(string word, bool search = true) {
        auto node = root;
        for (auto p:word) {
            if (node->next[p - 'a'])
                node = node->next[p - 'a'];
            else
                return false;
        }
        return search ? node->is_end : true;
    }

    bool startsWith(string prefix) {
        return search(prefix, false);
    }
};
# Python3
class Trie:
    class TrieNode:
        def __init__(self):
            self.is_end = False
            self.next = [None for _ in range(26)]

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

    def insert(self, word: str) -> None:
        node = self.root
        for w in word:
            if not node.next[ord(w) - ord('a')]:
                node.next[ord(w) - ord('a')] = self.TrieNode()
            node = node.next[ord(w) - ord('a')]
        node.is_end = True

    def search(self, word: str, search: bool = True) -> bool:
        node = self.root
        for w in word:
            if node.next[ord(w) - ord('a')]:
                node = node.next[ord(w) - ord('a')]
            else:
                return False
        return node.is_end if search else True

    def startsWith(self, prefix: str) -> bool:
        return self.search(prefix, False)
comments powered by Disqus