181 - 208 实现前缀树Trie

题目

实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。

示例:

Trie trie = new Trie();

trie.insert("apple"); trie.search("apple"); // 返回 true trie.search("app"); // 返回 false trie.startsWith("app"); // 返回 true trie.insert("app"); trie.search("app"); // 返回 true

说明:

• 你可以假设所有的输入都是由小写字母 a-z 构成的。

• 保证所有输入均为非空字符串。

解答

https://leetcode-cn.com/problems/implement-trie-prefix-tree/solution/shi-xian-trie-qian-zhui-shu-by-leetcode/

题解把前缀树应用说的很好呀，搜索自动补全、打字预测等等。

前缀树，就是根据字符串前缀来匹配的，数据结构。

xiaoneng

哈希表嵌套

https://leetcode.com/problems/implement-trie-prefix-tree/discuss/58834/AC-Python-Solution

每个字母都是一个key，嵌套哈希表。

最后推入一个#，来表明单词的结束。不然app和apple就无法区分了。

class Trie:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.data = {}

    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        d = self.data
        for w in word:
            if w not in d:
                d[w] = {}
            d = d[w]
        d["#"] = '#'

    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        return self.startsWith(word+"#")

    def startsWith(self, prefix: str) -> bool:
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        d = self.data
        for w in prefix:
            if w not in d:
                return False
            else:
                d = d[w]
        return True

Runtime: 112 ms, faster than 99.90% of Python3 online submissions for Implement Trie (Prefix Tree).

Memory Usage: 26.1 MB, less than 66.67% of Python3 online submissions for Implement Trie (Prefix Tree).

用node

https://leetcode-cn.com/problems/implement-trie-prefix-tree/solution/trie-tree-de-shi-xian-gua-he-chu-xue-zhe-by-xiao-x/

class TrieNode:
    def __init__(self):
        from collections import defaultdict
        self.children = defaultdict(TrieNode)
        self.isEnd = False


class Trie:
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        node = self.root
        for w in word:
            node = node.children[w]
        node.isEnd = True

    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        node = self.root
        for w in word:
            node = node.children.get(w)
            if node is None:
                return False
        return node.isEnd

    def startsWith(self, prefix: str) -> bool:
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        node = self.root
        for w in prefix:
            node = node.children.get(w)
            if node is None:
                return False
        return True

Runtime: 216 ms, faster than 32.09% of Python3 online submissions for Implement Trie (Prefix Tree).

Memory Usage: 31.5 MB, less than 7.41% of Python3 online submissions for Implement Trie (Prefix Tree).