【LeetCode-中等题】208. 实现 Trie (前缀树)

这篇具有很好参考价值的文章主要介绍了【LeetCode-中等题】208. 实现 Trie (前缀树)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目

【LeetCode-中等题】208. 实现 Trie (前缀树),力扣,# 中等题,leetcode,算法,职场和发展

方法一:利用数组构建26叉树

插入图示:
【LeetCode-中等题】208. 实现 Trie (前缀树),力扣,# 中等题,leetcode,算法,职场和发展
全搜索和前缀搜索:
注意:全局匹配匹配完直接返回插入时的标志位
而前缀匹配时,匹配成功后直接返回true 因为不需要往下匹配了

匹配到空trie都统统直接返回false
【LeetCode-中等题】208. 实现 Trie (前缀树),力扣,# 中等题,leetcode,算法,职场和发展

// 方法一  : 利用数组存储孩子节点
    private Trie[] children ; //孩子数组  
    private boolean isWord ; //标志位

    public Trie() {//构造函数
        children = new Trie[26];// 初始化为大小为26的数组
        isWord = false;//标志位初始化为false
    }
    
   
   //插入操作
    public void insert(String word) {
      Trie root  = this;//给祖先节点赋空对象//此时 孩子数组为空  标志位默认false
      for(int i = 0 ; i<word.length() ; i++){//一个一个拆分字符串,将字符 - 'a' 转换为坐标
        char ch = word.charAt(i);
        int idx = ch - 'a';
        if(root.children[idx] == null){  //如果发现当前位置 为null  则是第一次插入,创建新的trie
          root.children[idx] = new Trie();
        }
        root = root.children[idx]; //如果当前位置存在,那么将指针指向下一层
      }
      root.isWord = true;  //插入完成  标记为true
    }
    //全匹配操作
    public boolean search(String word) {
      Trie root  = this;//获得当前对象
      for(int i = 0 ; i<word.length() ; i++){//一个一个拆分字符串,将字符 - 'a' 转换为坐标
        char ch = word.charAt(i);
        int idx = ch - 'a';
        if(root.children[idx] == null){  //如果发现当前位置 为null  说明搜索不到  直接return fasle
         return false;
        }
        root = root.children[idx]; //如果当前位置存在,那么将指针指向下一层继续搜索
      }
      return root.isWord;//如果能搜索到 则直接就是返回本来的状态值

    }
    // 前缀匹配
    public boolean startsWith(String prefix) {
      Trie root  = this;//获得当前对象
      for(int i = 0 ; i<prefix.length() ; i++){//一个一个拆分字符串,将字符 - 'a' 转换为坐标`在这里插入代码片`
        char ch = prefix.charAt(i);
        int idx = ch - 'a';
        if(root.children[idx] == null){  //如果发现当前位置 为null  说明搜索不到  直接return fasle
         return false;
        }
        root = root.children[idx]; //如果当前位置存在,那么将指针指向下一层继续搜索
      }
      return true;//如果能搜索到 则直接就是返回true
    }

方法二:利用哈希表构建26叉树

相比较上面的用数组构建26叉树,其实也可以采用哈希表存储子节点

【LeetCode-中等题】208. 实现 Trie (前缀树),力扣,# 中等题,leetcode,算法,职场和发展

方法二  : 利用hashmap存储孩子节点

    private Map<Character,Trie> children ; //孩子哈希表  key 为父节点  value为子trie节点  
    private boolean isWord ; //标志位

    public Trie() {//构造函数
        children = new HashMap<>();// 初始化哈希表
        isWord = false;//标志位初始化为false
    }
    
   
   //插入操作
    public void insert(String word) {
      Trie root  = this;//给祖先节点赋空对象
      for(int i = 0 ; i<word.length() ; i++){//一个一个拆分字符串,将字符 - 'a' 转换为坐标
        char ch = word.charAt(i);
        Trie node = root.children.get(ch);
       
        if(node == null){  //如果发现当前位置 为null  则是第一次插入,创建新的trie
          root.children.put(ch,new Trie());
        }
        root = root.children.get(ch); //如果当前位置存在,那么将指针指向下一层
      }
      root.isWord = true;  //插入完成  标记为true
    }
    //全匹配操作
    public boolean search(String word) {
      Trie root  = this;//获得当前对象
      for(int i = 0 ; i<word.length() ; i++){//一个一个拆分字符串,将字符 - 'a' 转换为坐标
        char ch = word.charAt(i);
        Trie node = root.children.get(ch);
        if(node == null){  //如果发现当前位置 为null  说明搜索不到  直接return fasle
         return false;
        }
        root = root.children.get(ch); //如果当前位置存在,那么将指针指向下一层继续搜索
      }
      return root.isWord;//如果能搜索到 则直接就是返回本来的状态值

    }
    // 前缀匹配
    public boolean startsWith(String prefix) {
      Trie root  = this;//获得当前对象
      for(int i = 0 ; i<prefix.length() ; i++){//一个一个拆分字符串,将字符 - 'a' 转换为坐标
       char ch = prefix.charAt(i);
        Trie node = root.children.get(ch);
        if(node == null){  //如果发现当前位置 为null  说明搜索不到  直接return fasle
         return false;
        }
       root = root.children.get(ch); //如果当前位置存在,那么将指针指向下一层继续搜索
      }
      return true;//如果能搜索到 则直接就是返回true
    }

参考:Leetcode 208 实现Trie(前缀树)文章来源地址https://www.toymoban.com/news/detail-706226.html

到了这里,关于【LeetCode-中等题】208. 实现 Trie (前缀树)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 力扣208题:实现Tire(前缀树)

    力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 设计一个前缀节点类,这个类保存了,当前字符所在层级,是否为某个词的词尾,以及后续所有字符的节点,采用HashMap存储,key是后续字符,value就是下一个节点对象; 1 字符所在层级level变量的设计:因为词的匹配不光要

    2024年01月21日
    浏览(38)
  • LeetCode_前缀树_中等_1268.搜索推荐系统

    给你一个产品数组 products 和一个字符串 searchWord ,products 数组中每个产品都是一个字符串。 请你设计一个推荐系统,在依次输入单词 searchWord 的每一个字母后,推荐 products 数组中前缀与 searchWord 相同的最多三个产品。如果前缀相同的可推荐产品超过三个,请按字典序返回最

    2024年02月16日
    浏览(39)
  • LeetCode 2090. K Radius Subarray Averages【前缀和,滑动窗口,数组】中等

    本文属于「征服LeetCode」系列文章之一,这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁,本系列将至少持续到刷完所有无锁题之日为止;由于LeetCode还在不断地创建新题,本系列的终止日期可能是永远。在这一系列刷题文章中,我不仅会讲解多种解题思路及其优化,

    2024年02月11日
    浏览(44)
  • 【LeetCode力扣】11. 盛最多水的容器 (中等)

      目录 1、题目介绍 2、解题 2.1、解题思路  2.2、图解说明  2.3、解题代码 原题链接: 11. 盛最多水的容器 - 力扣(LeetCode) 示例 2: 提示: n == height.length 2 = n = 105 0 = height[i] = 104 这道题最优的方法就是用双指针,我们可以用指针 left 和指针 right 分别指向数组 height[ ] 的第一

    2024年02月06日
    浏览(46)
  • 算法第十八天-实现Trie(前缀树)

    本文是前缀入门教程 从二叉树说起 前缀树,也是一种树。为了理解前缀树,我们先从二叉树说起。常见的二叉树结构是下面这样子的: 可以看到一个树的节点包含了三个元素:该节点本身的值,左子树的指针,右子树的指针。二叉树可视化是下面这样子的: 二叉树的每个节

    2024年01月18日
    浏览(33)
  • LeetCode 2811. Check if it is Possible to Split Array【脑筋急转弯;前缀和+动态规划或记忆化DFS】中等

    本文属于「征服LeetCode」系列文章之一,这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁,本系列将至少持续到刷完所有无锁题之日为止;由于LeetCode还在不断地创建新题,本系列的终止日期可能是永远。在这一系列刷题文章中,我不仅会讲解多种解题思路及其优化,

    2024年02月13日
    浏览(33)
  • 【贪心算法】Leetcode 55. 跳跃游戏【中等】

    给你一个非负整数数组 nums ,你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个下标,如果可以,返回 true ;否则,返回 false 。 示例 1: 输入 :nums = [2,3,1,1,4] 输出: true 解释 :可以先跳 1 步,从下标

    2024年04月28日
    浏览(50)
  • LeetCode_贪心算法_中等_763.划分字母区间

    给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段,同一字母最多出现在一个片段中。注意,划分结果需要满足:将所有划分结果按顺序连接,得到的字符串仍然是 s。返回一个表示每个字符串片段的长度的列表。 示例 1: 输入:s = “ababcbacadefegdehijhklij” 输出

    2024年02月14日
    浏览(75)
  • Grind75第13天 | 208.实现Trie、54.螺旋矩阵、721.账户合并

    题目链接:https://leetcode.com/problems/implement-trie-prefix-tree 解法: 这个题非常经典,背下来。 首先需要自己实现Node的类,属性为children和是否为单词的标记,再去初始化Trie的类。 在插入和查询的过程中,都要不断让指针指向children。 参考题解:实现Trie 边界条件:无 题目链接:

    2024年01月20日
    浏览(42)
  • [Java·算法·中等] LeetCode122. 买股票的最佳时机 II 解读

    人不走空                                                                          目录         🌈个人主页:人不走空       💖系列专栏:算法专题 ⏰诗词歌赋:斯是陋室,惟吾德馨 题目 示例 示例1 示例2 示例3  提示  详细解读 作者其他作品:   给你一

    2024年02月19日
    浏览(33)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包