实现 Trie (前缀树)

Leetcode Link: 208. 实现 Trie (前缀树) - 力扣（LeetCode）

题目

Trie（发音类似 “try”）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。

请你实现 Trie 类：

• Trie() 初始化前缀树对象。
• void insert(String word) 向前缀树中插入字符串 word 。
• boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
• boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。

解法一

思路： 首先要清楚什么是 Trie 树，与二叉树相比

1. 一个节点的孩子节点数上限是 2
2. 每个节点只保存一个字符

仿照二叉树的构建，一般需要 val 和 next 两个变量构成一个节点。

这里，使用字典可以简化这一步骤，即 TrieNode 可以定义为

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = False

• is_word是什么，有什么用? 用来指示以上一个节点字符结束时组成的字符串是不是一个完整的单词。 我们知道Trie树可以用来快速填充，比如说你想打apple，当你输入到app时，程序应该提醒你可能的单词，如apple, approach，而不能提醒你 appl 这种不是单词的词（没有is_word就可能会提醒这种）。即is_word可以告诉你那些是单词。
• children是字典，怎么使用？怎么表示类似二叉树中val和next? 我们知道，在Trie树中，val应该是当前节点存的什么字符，next指向下一个节点。这里使用了字典，事情变的简单了，但是有一点点绕。注意到children是个字典，字典的key用来表示当前节点的val，childern[val]的值(value)来表示下一个节点。

题解：

class Trie:
    def __init__(self):
        self.root = TrieNode()
 
    def insert(self, word: str) -> None:
        node = self.root
        for c in word:
            if c not in node.children:
                node.children[c] = TrieNode()
            node = node.children[c]
        node.is_word = True
 
    def search(self, word: str) -> bool:
        node = self.root
        for c in word:
            if c not in node.children:
                return False
            node = node.children[c]
        return True if node.is_word else False
        
    def startsWith(self, prefix: str) -> bool:
        node = self.root
        for c in prefix:
            if c not in node.children:
                return False
            node = node.children[c]
        return True
 
class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = False
 
# 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)

解法二

思路： 上面的为字典实现，更简单。

此为标准实现，标准且复杂。

题解：

# 标准实现
class Trie(object):
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = TrieNode()
 
    def insert(self, word):
        """
        Inserts a word into the trie.
        :type word: str
        :rtype: None
        """
        node = self.root
        for i in range(len(word)):
            if not node.containsKey(word[i]):
                node.put(word[i], TrieNode())
            node = node.get(word[i])
        node.is_word = True
 
    def searchPrefix(self, word):
        node = self.root
        for i in range(len(word)):
            if node.containsKey(word[i]):
                node = node.get(word[i])
            else:
                return None
        return node
 
    def search(self, word):
        """
        Returns if the word is in the trie.
        :type word: str
        :rtype: bool
        """
        node = self.searchPrefix(word)
        return node is not None and node.is_word
 
    def startsWith(self, prefix):
        """
        Returns if there is any word in the trie that starts with the given prefix.
        :type prefix: str
        :rtype: bool
        """
        node = self.searchPrefix(prefix)
        return node is not None
 
 
class TrieNode:
    def __init__(self):
        self.__R = 26
        self.is_word = False
        self.links = [None] * self.__R
 
    def containsKey(self, ch):
        return self.links[ord(ch) - ord('a')] is not None
 
    def get(self, ch):
        return self.links[ord(ch) - ord('a')]
 
    def put(self, ch, node):
        self.links[ord(ch) - ord('a')] = node
 

启发和联系