《数据结构与算法》总结（九）Trie

目录

• Trie简介
• 接口设计
• 总结

一 Trei 简介

image

二 接口设计

- (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自动机

---

项目链接地址 - 19_Trie

作为一个开发者，有一个学习的氛围跟一个交流圈子特别重要，这是一个我的iOS交流群：413038000，不管你是大牛还是小白都欢迎入驻 ，分享BAT,阿里面试题、面试经验，讨论技术， 大家一起交流学习成长！

以下资料在群文件可自行下载！

推荐阅读

iOS开发——最新 BAT面试题合集（持续更新中）

作者：路飞_Luck
链接：https://www.jianshu.com/p/37a783ab1d32
来源：简书