目录
- Trie简介
- 接口设计
- 总结
一 Trei 简介
image.png
二 接口设计
- (int)size;
- (bool)isEmpty;
- (void)clear;
- (bool)contains:(NSString *)str;
- (void)add:(NSString *)str;
- (void)remove:(NSString *)str;
- (bool)starsWith:(NSString *)prefix;
- 测试代码
- (void)test {
Trie *trie = [[Trie alloc] init];
[trie add:@"cat" value:@(1)];
[trie add:@"dog" value:@(2)];
[trie add:@"catalog" value:@(3)];
[trie add:@"cast" value:@(4)];
NSString *prefix = @"cat";
// prefix = @"dog";
// prefix = @"catalog";
// prefix = @"cast";
NSLog(@"starsWith:%@ %d",prefix,[trie starsWith:prefix]);
}
- 运行结果如下
2020-03-14 17:22:36.567671+0800 19_Trie[71552:8058556] starsWith:cat 1
三 总结
Trie 的优点 搜索前缀的效率主要跟前缀的长度有关
*Trie 的缺点 需要耗费大量的内存，因此还有待改进
更多Trie 相关的数据结构和算法
Double-array Trie、Suffix Tree、Patricia Tree、Crit-bit Tree、AC自动机
本文参考 MJ老师的 恋上数据结构与算法
本人技术水平有限，如有错误欢迎指正。
书写整理不易，您的打赏与点赞是对我最大的支持和鼓励。
