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

上一页207.课程表下一页209. 长度最小的子数组

最后更新于2年前

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

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

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

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

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

...

count[i]

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