前缀树（Tire）

核心思想

空间换时间，是一种用于快速减速的多叉树结构，利用字符串的公共前缀来降低时间

优缺点：

优点：查询效率高，减少字符比较

缺点：内存消耗较大

每次都会从头向下一直到字符串结尾

前缀树

1 单个字符串从前到后加到一棵多叉树上

2 每隔字符串都会有自己所在节点的两个属性path和end，path代表经过，end代表这个字符结尾

3 所有的插入操作都是一样的插入方式，有就复用没有就新开辟一条路

4 经过节点path += 1 ；每个字符串结尾 end += 1

5 可以快速查询前缀和完全匹配的数量

画图解释

如图所示我们插入第一个字符串“abc”，从a开始，没有a就开辟一个a的路把经过的地方都标记path += 1

结果相同方式遍历b和c，最后c结果end +=1

相同的方式插入ab，每次都会从头开始第一个起始点path += 1，a存在a的path += 1，b也存在b的path +=1 ，b是结尾所以b的end +=1

实现

两种方式实现，第一种会用列表来储存，一种会用字典来储存

实现方式都一样，看会一种即可。

第一种

class Trie:

    def __init__(self):

        """

        Initialize your data structure here.

        """

        self.children = [None] * 26

        self.path = 0

        self.isEnd = 0

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

        """

        Inserts a word into the trie.

        """

        node = self

        node.path += 1

        for ch in word:

            offset = ord(ch) - ord('a')

            # node.path += 1

            if not node.children[offset]:

                node.children[offset] = Trie()

            node = node.children[offset]

            node.path += 1

        node.isEnd += 1

    def startsWith(self, prefix: str) :

        node = self

        for ch in prefix:

            offset = ord(ch) - ord('a')

            if not node.children[offset]:

                return None

            node = node.children[offset]

        return node.path

    def search(self, prefix: str) :

        node = self

        for ch in prefix:

            offset = ord(ch) - ord('a')

            if not node.children[offset]:

                return None

            node = node.children[offset]

        return node.isEnd

第二种

class Trie:

    def __init__(self):

        """

        Initialize your data structure here.

        """

        self.children = dict()

        self.path = 0

        self.isEnd = 0

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

        """

        Inserts a word into the trie.

        """

        node = self

        node.path += 1

        for ch in word:

            offset = ord(ch) - ord('a')

            if offset not in node.children:

                node.children[offset] = Trie()

            node = node.children[offset]

            node.path += 1

        node.isEnd += 1

    def startsWith(self, prefix: str) :

        node = self

        for ch in prefix:

            offset = ord(ch) - ord('a')

            if offset not in node.children:

                return None

            node = node.children[offset]

        return node.path

    def search(self, prefix: str) :

        node = self

        for ch in prefix:

            offset = ord(ch) - ord('a')

            if offset not in node.children:

                return None

            node = node.children[offset]

        return node.isEnd

巴特西

前缀树（Tire）—Python

核心思想

优缺点：

前缀树

画图解释

实现

最新文章

热门文章