本文主要是介绍[LeetCode] 208. Implement Trie (Prefix Tree)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目内容
https://leetcode-cn.com/problems/implement-trie-prefix-tree/
Implement a trie with insert, search, and startsWith methods.
Example:Trie trie = new Trie();trie.insert("apple");
trie.search("apple"); // returns true
trie.search("app"); // returns false
trie.startsWith("app"); // returns true
trie.insert("app");
trie.search("app"); // returns true题目思路
这道题目是要实现一个前缀树的情况。前缀树就是如果结构中已经存在一个单词，那么输入这个单词的前缀，可以通过一种方法来查询到。因为题目给出的内容是小写字母组成的单词，所以我们可以用开头字母作为索引，这种方法就是想哈希表中的链表方法。与此同时，使用defaultdict可以避免错误抛出。
程序代码
from collections import defaultdict
class Trie(object):def __init__(self):"""Initialize your data structure here."""self.dict=defaultdict(list)def insert(self, word):"""Inserts a word into the trie.:type word: str:rtype: None"""self.dict[word[0]].append(word)def search(self, word):"""Returns if the word is in the trie.:type word: str:rtype: bool"""if word in self.dict[word[0]]:return Truereturn Falsedef startsWith(self, prefix):"""Returns if there is any word in the trie that starts with the given prefix.:type prefix: str:rtype: bool"""l=len(prefix)for i in self.dict[prefix[0]]:if prefix==i[:l]:return Trueelse:return False
这篇关于[LeetCode] 208. Implement Trie (Prefix Tree)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
