• 字典树
  • 树节点
  • 代码实现

字典树

字典树主要解觉单词的前缀搜索，由于单词重复字母比较多，如果使用哈希空间会比较大，而且也不支持前缀搜索

Trie树，即字典树，⼜又称单词查找树或键树，是⼀一种树形结构，是⼀一种哈希树的变种。典型应⽤用是⽤用于统计和排序⼤大量量的字符串串（但不不仅限于字符串串），所以经常被搜索引擎系统⽤用于⽂文本词频统计。

它的优点是：最⼤大限度地减少⽆无谓的字符串串⽐比较，查询效率⽐比哈希表⾼高。

Trie的核⼼心思想是空间换时间。利利⽤用字符串串的公共前缀来降低查询时间的开销以达到提⾼高效率的⽬目的。

特点：

1. 根节点不不包含字符，除根节点外每⼀个节点都只包含一个字符。
2. 从根节点到某⼀节点，路路径上经过的字符连接起来，为该节点对应的字符串串。
3. 每个节点的所有⼦子节点包含的字符都不不相同。

树节点

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

代码实现

class Trie:

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

    def insert(self, word: str) -> None:
        cur = self.root
        for x in word:
            if x not in cur.children:
                cur.children[x] = TrieNode()
            cur = cur.children[x]
        cur.is_word = True

    def search(self, word: str) -> bool:
        cur = self.root
        for x in word:
            if x not in cur.children:
                return False
            cur = cur.children[x]

        return cur.is_word

    def startsWith(self, prefix: str) -> bool:
        cur = self.root
        for x in prefix:
            if x not in cur.children:
                return False
            cur = cur.children[x]

        return True

– END –