Jianbo Dai's

lc208.实现Trie（前缀树）

 
  • Mar 15, 2021

题目链接

复习一下前缀树。实现如下所示。Trie树是一个有根的树，其结点具有以下字段：1.最多R个指向字节点的链接，其中每个链接对应字母表数据集中的一个字母。这里假定R为26为小写拉丁字母的个数。2.布尔字段，以指定节点是对应键的结尾还是只是键前缀。Trie树中最常见的两个操作是键的插入和查找。先说向Trie树中插入键，我们通过搜索Trie树来插入一个键，我们从根开始搜索它对应于第一个键字符的链接。有两种情况：1.链接存在。沿着链接移动到下一个树的下一个子层。算法继续搜索下一个键字符。2.链接不存在。创建一个新的结点，并将它与父结点的链接相连，该链接与当前的键字符相匹配。重复以上步骤直到到达键的最后一个字符，然后将当前结点标记为结束结点，算法完成。插入的时间复杂度和空间复杂度都为O（M），M为键长。接着我们考虑在Trie树中查找键，每个键在Trie中表示为从根结点到内部结点或叶的路径。我们用第一个键字符从根开始，检查当前结点中与键字符对应的链接。有两种情况：1.存在链接，我们就移动到该链接后面路径中的下一个结点，并继续搜索下一个键字符。2.不存在链接。若已无键字符，且当前结点标记为isEnd，则返回True，否则要么还有键字符剩余但无法跟随Trie树的键路径，找不到键，或者没有键字符剩余了，当当前结点没有标记为isEnd，也就是说带查找键只是树中另一个键的前缀，这样的时候会返回False。查找键的时间复杂度是O（M），空间复杂度为O（1）。第三种情况是查找Trie树中的键前缀，该方法与在Trie树中搜索键时类似，唯一区别是在到达键前缀的末尾时，总是返回True，我们不需要考虑当前Trie结点是否用了“isEnd”标记。时间复杂度和空间复杂度和查找完整键一样。

python:

class Trie:

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


    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        tree = self.lookup
        for a in word:
            if a not in tree:
                tree[a] = {}
            tree = tree[a]
        # symbol of word ending
        tree["#"] = "#"


    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        tree = self.lookup
        for a in word:
            if a not in tree:
                return False
            tree = tree[a]
        if "#" in tree:
            return True
        return False


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


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