leetcode 208 Implement Trie (Prefix Tree)解题笔记--不断简化的多个版本
题目要求实现一个基本的trie数据结构，也称为前缀树，
要求实现insert, search, startWith三个接口，
其中所有的输入字符串的字符都是a-z
解题思路分析
- trie的基本结构是一个多叉树， 每个节点表示一个字符， 然后从根节点到叶节点的完整路径表示一个字符串。
比如这里有一个比较详细的介绍。
https://www.cnblogs.com/huangxincheng/archive/2012/11/25/2788268.html - trie的主要用处： 字符串匹配， 前缀匹配, 还可以在上面加上额外信息，比如加上频率，然后可以做词频统计等
- trie的主要实现， 每个节点会有多个children， 然后每次添加一个新的字符串的时候， 逐个字符访问node走下来， 如果到某一个节点的时候字符如果不存在，那么就添加一个新的节点, 然后一路下去。
Read full article from leetcode 208 Implement Trie (Prefix Tree)解题笔记--不断简化的多个版本
No comments:
Post a Comment