Posts List

一周LeetCode习题精选

LeetCode 208 链接:Implement Trie (Prefix Tree) 本题要求构造一个前缀树。前缀树是数据结构中树的一种,用于检索字符串数据集中的值,在自动完成、拼写检查、IP路由等方面都有应用。前缀树节点有两个字段:一个链接到字符串的下一个字符节点child,另一个为布尔值is_end,判断指定节点是否已到末尾。这里需要说一下Python的collections.defaultdict()这个方法,此方法构建了一个类似字典的对象,与普通字典不同的是,在查找字典中不存在key时,普通字典会报错,而defaultdict不会返回错误,而是返回一个默认值。本例会返回一个TrieNode节点,这样省去了在功能方法中新建节点的步骤。本题要求实现三个前缀树的三个功能:插入单词、搜索给定单词是否存在于前缀树以及搜索给定单词是否是前缀树中单词的前缀。