Leetcode刷题 - task2 - 字典树知识

1. 字典树知识：

简介：

字典树（Trie）：又称为前缀树、单词查找树，是一种树形结构。顾名思义，就是一个像字典一样的树。它是字典的一种存储方式。字典中的每个单词在字典树中表现为一条从根节点出发的路径，路径相连的边上的字母连起来就形成对应的字符串。

它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。

性质：

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

示例：

基本操作：

字典树的基本操作有 创建、插入、查找 和 删除。其中删除操作是最不常用，我们这里主要介绍字典树的创建、插入和查找。

字典树的节点结构：

首先，来定义一下字典树的节点结构，这里即可以使用数组，也可以使用哈希表来表示当前节点的多个子节点。

class Node:
    # 初始化字符节点
    def __init__(self):
        # 初始化子节点
        self.children = dict()
        # 或者 self.children = {}
        # 如果使用数组：self.children = [None for _ in range(26)]

        # isEnd 用来标记单词结束
        self.isEnd = False

字典树的基本结构：

在字典树的初始化操作时，定义一个根节点。这个根节点不用保存字符，在后续进行插入操作、查找操作都是从字典树的根节点开始的。

class Trie:
    # 初始化字典树
    def __init__(self):
        # 初始化根节点（根节点不保存字符）
        self.root = Node()

字典树的插入操作：

    def insert(self, word):
        cur = self.root 
        for ch in word:
            if ch not in cur.children:
                cur.children[ch] = Node() 
            cur = cur.children[ch]
        cur.isEnd = True

字典树的查找单词操作：

    def search(self, word):
        cur = self.root 
        for ch in word:
            if ch not in cur.children:
                return False 
            cur = cur.children[ch]
        return cur is not None and cur.isEnd

字典树的查找前缀操作：

    def startsWith(self, prefix):
        cur = self.root
        for ch in prefix:
            if ch not in cur.children:
                return False
            cur = cur.children[ch]
        return cur is not None

整理一下，就可以得到字典树的Python的代码实现。

class Node:
    def __init__(self):
        self.children = dict()
        self.isEnd = False 


class Trie:
    def __init__(self):
        self.root = Node()
    
    def insert(self, word):
        cur = self.root 
        for ch in word:
            if ch not in cur.children:
                cur.children[ch] = Node()
            cur = cur.children[ch]
        cur.isEnd = True 
    
    def search(self, word):
        cur = self.root 
        for ch in word:
            if ch not in cur.children:
                return False 
            cur = cur.children[ch]
        return cur is not None and cur.isEnd 
    
    def startsWith(self, prefix):
        cur = self.root 
        for ch in prefix:
            if ch not in cur.children:
                return False
            cur = cur.children[ch]
        return cur is not None

2. 相关LeetCode例题：

$\begin{array}{c|c|c|c|c} \hline \text{题号} & \text{标题} & \text{题解链接} & \text{标签} & \text{难度}\\ \hline \text{0208} & \text{实现 Trie (前缀树)} & \text{Python} & \text{设计、字典树、哈希表、字符串} & \text{中等}\\ \text{0677} & \text{键值映射} & \text{Python} & \text{设计、字典树、哈希表、字符串} & \text{中等}\\ \text{1023} & \text{驼峰式匹配} & \text{Python} & \text{字典树、双指针、字符串、字符串匹配} & \text{中等}\\ \text{0211} & \text{添加与搜索单词 - 数据结构设计} & \text{Python} & \text{深度优先搜索、设计、字典树、字符串} & \text{中等}\\ \text{0648} & \text{单词替换} & \text{Python} & \text{字典树、数组、哈希、字符串} & \text{中等}\\ \text{0676} & \text{实现一个魔法字典} & \text{Python} & \text{设计、字典树、哈希表、字符串} & \text{中等}\\ \hline \end{array}$