美文网首页
《恋上数据结构与算法一》笔记(十九)Trie

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

作者: 路飞_Luck | 来源:发表于2020-03-14 17:26 被阅读0次
    目录
    • 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老师的 恋上数据结构与算法


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


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


    相关文章

      网友评论

          本文标题:《恋上数据结构与算法一》笔记(十九)Trie

          本文链接:https://www.haomeiwen.com/subject/fissdhtx.html