前缀树（Trie树）

【前缀树】(Trie Tree) 是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串）。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。

前缀树又名字典树、单词查找树。如下图

实现

root节点

孩子节点： Hashmap : key = 字符， val = 新的前缀树

结束flag: bool

采用字典嵌套的方式来实现前缀树，其中跟字典下面的keys()表示首字母可能的情况，每个key对应的val均为一个字典，表示该key的下一个字符的可能字符.

例 words ="apple", "app", "go", "good", "google" 采用字典树如下表示

具提存储方式如下：


{ "a" :{"p" :{ "p":{},
                "l":{"e" :{"isEnd"} }
                "isEnd"
            }
 "g" :{"o":{"isEnd"
            "o":{ "g":{"l":{"e":{"isEnd"}}}
                    "d":{"isEnd"}
                }
            }
     }
   }
}

python实现

✉️

208. 实现 Trie (前缀树)

常用的三种方法

添加一个单词到树中 insert

查找以以某字符串为前缀的单词 search_prefix

查找是否处存在某前缀的单词 startsWith

搜索某个单词是否在树中 search


class Trie(object):
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = TrieNode()

    def insert(self, word):
        """
        Inserts a word into the trie.
        :type word: str
        :rtype: None
        """
        node = self.root
        for c in word:
            if c not in node.children:
                node.children[c] = TrieNode()
            node = node.children[c]
        node.is_word = True

    def search_prefix(self, word):
        node = self.root
        for c in word:
            if c not in node.children:
                return None
            node = node.children[c]
        return node

    def search(self, word):
        """
        Returns if the word is in the trie.
        :type word: str
        :rtype: bool
        """
        node = self.search_prefix(word)
        return node is not None and node.is_word

    def startsWith(self, prefix):
        """
        Returns if there is any word in the trie that starts with the given prefix.
        :type prefix: str
        :rtype: bool
        """
        return self.search_prefix(prefix) is not None


class TrieNode(object):
    def __init__(self):
        self.children = {}
        self.is_word = False