《恋上数据结构与算法一》笔记（十九）Trie

目录

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

---

项目链接地址 - 19_Trie

---

本文参考 MJ老师的 恋上数据结构与算法

---

《恋上数据结构与算法一》笔记

---

本人技术水平有限，如有错误欢迎指正。
书写整理不易，您的打赏与点赞是对我最大的支持和鼓励。

---