思想

1. Trie树是用来快速存储和查找字符串集合的数据结构
2. 使用到Trie树的题，字符一般都是同个类型（比如都是大写/都是小写/都是数字）
3. Trie树是一个字典

如何存储字符串集合

• 每个字符从前遍历，trie树从根结点出发，依次建树

• 给每个单词的结尾字符都打上标记

如何查找字符串集合

给定一个字符，查询是否在字符串集合里面，就可以根据给定的字符遍历树

代码实现

无注释版本

N = 100010
son = [[0 for _ in range(26)]for _ in range(N)]
cnt = [0] * N 
idx = 0 
def insert(str):
    global son
    global cnt
    global idx
    p = 0 # 从根结点开始走
    for i in range(len(str)):
        u = ord(str[i]) - ord('a') 
        if not son[p][u]: 
            idx += 1 
            son[p][u] = idx 
        p = son[p][u] 
    cnt[p] += 1 

def search(str):
    global son
    global cnt
    global idx
    p = 0
    for i in range(len(str)):
        u = ord(str[i]) - ord('a')
        if not son[p][u]:
            return 0
        p = son[p][u]
    return cnt[p]

N = 100010 #假设字符串长度不超过N
# son[N][26]：每个点最多只能连6个字母
# son[i][j]表示插入的第i个字符的第j个儿子（a-z映射为0-25）是否存在，存在的话填写儿子的编号
# cut和 son 下标为0的点为根结点，也是空节点
son = [[0 for _ in range(26)]for _ in range(N)]
cnt = [0] * N # 存放以编号为i字符结尾的字符串数量
idx = 0 # 字符编号
def insert(str):
    global son
    global cnt
    global idx
    p = 0 # 从根结点开始走
    for i in range(len(str)):
        u = ord(str[i]) - ord('a') # 存当前字符的值，-‘a'是映射到0-25中
        if not son[p][u]: # 如果当前节点没有该儿子的话，就把它创建出来
            idx += 1 # 新插入的节点编号为idx+1
            son[p][u] = idx # 存新儿子的编号
        p = son[p][u] # 有该儿子之后就继续往下走
    cnt[p] += 1 # p走到结尾了，以p结尾的单词+1

def search(str):
    global son
    global cnt
    global idx
    p = 0
    for i in range(len(str)):
        u = ord(str[i]) - ord('a')
        if not son[p][u]:
            return 0
        p = son[p][u]
    return cnt[p]