208.实现Trie(前缀树)

208. 实现 Trie (前缀树)

Trie树（又叫「前缀树」或「字典树」）是一种用于快速查询「某个字符串/字符前缀」是否存在的数据结构。

其核心是使用「边」来代表有无字符，使用「点」来记录是否为「单词结尾」以及「其后续字符串的字符是什么」。

图片

一、二维数组（不易理解）

• 使用二维数组trie[] 来存储所有的单词字符。

• 使用 index来自增记录到底用了多少个格子（相当于给被用到格子进行编号）。

• 使用 count数组记录某个格子被「被标记为结尾的次数」（当 idx编号的格子被标记了n次，则有 count[idx]=n）。

  如插入”apple“、”ape“后，trie数组、count数组如下：

  	a	b	c	d	e	...	l	...	p	...	z	count[i]
  0	1	0	0	0	0		0		0		0	0
  1	0	0	0	0	0		0		2		0	0
  2	0	0	0	0	6		0		3		0	0
  3	0	0	0	0	0		4		0		0	0
  4	0	0	0	0	5		0		0		0	0
  5	0	0	0	0	0		0		0		0	1
  6	0	0	0	0	0		0		0		0	1

class Trie:

    def __init__(self):
        self.N = 100000
        # 存储所有字符
        self.trie = [[0] * 26 for _ in range(self.N)]
        self.count = [0] * self.N
        self.index = 0
    
    # 实现插入
    def insert(self, word: str) -> None:
        # 横轴表示格子，纵轴表示字符
        # trie[i][j]表示要匹配的下一个格子序号
        i = 0	# 格子从0开始
        for s in word:
            j = ord(s) - ord('a')
            # 格子为0表示没匹配过
            if self.trie[i][j] == 0:
                # 使用的格子数+1
                self.index += 1
                self.trie[i][j] = self.index
            i = self.trie[i][j]
        # 统计i处的格子作为结尾的个数
        self.count[i] += 1

    # 实现搜索
    def search(self, word: str) -> bool:
        i = 0
        for s in word:
            j = ord(s) - ord('a')
            # 格子为0表示没匹配过
            if self.trie[i][j] == 0:
                return False
            # 否则匹配下一位
            i = self.trie[i][j]
        # 最后看i处格子被作为结尾的次数，只要不是0，都说明该字符串存在
        return self.count[i] != 0

    # 查找字典中是否有以prefix为前缀的字符串
    def startsWith(self, prefix: str) -> bool:
        i = 0
        for s in prefix:
            j = ord(s) - ord('a')
            # 格子为0表示没匹配过
            if self.trie[i][j] == 0:
                return False
            # 否则匹配下一位
            i = self.trie[i][j]
        # 与search函数的区别是，没有False，就是True
        return True

二、TrieNode（推荐）

定义数据结构TrieNode，是一个26叉树

# 数据结构，Trie树节点，表示一个字符
class TrieNode:
    def __init__(self):
        self.end = False	# 标志该字符是否为某个单词的结尾
        self.tns = [None] * 26	#记录该字符的后续字符，26个分支表示a-z，None表示无后续

class Trie:

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


    def insert(self, word: str) -> None:

        i = self.root
        for s in word:
            j = ord(s) - ord('a')
            if i.tns[j] == None:
                i.tns[j] = TrieNode()
            i = i.tns[j]
        i.end = True

    def search(self, word: str) -> bool:
        i = self.root
        for s in word:
            j = ord(s) - ord('a')
            if i.tns[j] == None:
                return False
            i = i.tns[j]
        return i.end

    def startsWith(self, prefix: str) -> bool:
        i = self.root
        for s in prefix:
            j = ord(s) - ord('a')
            if i.tns[j] == None:
                return False
            i = i.tns[j]
        return True