首页 > 其他分享 >208. 实现 Trie (前缀树)

208. 实现 Trie (前缀树)

时间:2024-04-01 18:48:40浏览次数:28  
标签:ch return 前缀 Trie 208 chs root public

class Trie {

    Trie[] chs= new Trie[26];
    int cnt = 0;

    public Trie() {

    }
    
    public void insert(String word) {
        Trie root = this;
        for(char ch : word.toCharArray()){
            if(root.chs[ch - 'a'] == null){
                root.chs[ch - 'a'] = new Trie();
            }
            root = root.chs[ch - 'a'];
        }
        root.cnt ++;
    }
    
    public boolean search(String word) {
        Trie root = this;
        for(char ch : word.toCharArray()){
            if(root.chs[ch - 'a'] == null)
                return false;
            root = root.chs[ch - 'a'];
        }
        return root.cnt != 0;
    }
    
    public boolean startsWith(String prefix) {
        Trie root = this;
        for(char ch : prefix.toCharArray()){
            if(root.chs[ch - 'a'] == null)
                return false;
            root = root.chs[ch - 'a'];
        }
        return true;
    }
}

标签:ch,return,前缀,Trie,208,chs,root,public
From: https://www.cnblogs.com/ganyq/p/18109126

相关文章

  • 前缀异或和
    异或是可以用前缀和来维护的,因为异或有一个重要的性质x^x=0设preXor[i]=a[0]^a[1]^a[2]^a[3]^a[4]^.....^a[i]那么给定一个[l,r]范围的区间求a[l,r]的异或和,我们就可以利用前缀异或和来求解preXor(l,r)=preXor(0,r)^preXor(0,l-1)=preXor[r]^p......
  • P2089 烤鸡
    题目链接:不要怕太暴力而不敢打()第一时间想到的其实是深搜,每个位置都有三种选择,考虑完当前位置后再顺次考虑接下来的位置。后来仔细一想,这不就是暴力枚举么!直接十重循环,每次看各个位置上的数之和是否等于\(n\),时间复杂度为\(3^{10}\)约为\(5e^4\),因此不会超时。#include<cs......
  • CF208E Blood Cousins
    CF208EBloodCousins线段树合并考虑把询问离线,转化题意,也就是求\(v\)的\(p\)级祖先有多少个\(p\)级儿子,那么询问的答案就是「\(p\)级祖先有多少个\(p\)级儿子数量-1」(减去自己)。\(p\)级祖先可以倍增找到。我们可以维护根节点的\(k\)级儿子。因为在遍历的过程中......
  • 杭电OJ 2084 数塔
    数塔题目明确告诉你,这是一道DP动态规划问题,那么首先先回顾什么是动态规划,就是把原问题分解为多个子问题,再记忆子问题的结果,来降低时间复杂度。观察这个数塔,首先设置一个数组dp[][],令\(dp[j][i]\)表示以第j层的第i个结点为终点的最大和,有以下3种情况:1.边界情况,结点\(i==0\)......
  • P6105 [Ynoi2010] y-fast trie
    [Ynoi2010]y-fasttrie-洛谷这道题让我学到了一些之前看过但没总结出来的\(trick\)显然加入集合中数要先取模对于\(x+y\geqC\)的部分,直接取最大和次大即可对于\(x+y<C\)的部分,我们先考虑暴力枚举\(x\),二分找到每一个\(y\)取最优即可若此题离线,考......
  • Leetcode 【930. 和相同的二元子数组】【统计「优美子数组」】【974. 和可被 K 整除的
    这道题目是经典的求子数组之和=goal的个数,用map维护。但是笔者在实现的过程中发现0的情况不是很好出来,问题在于mp[sum]和sum+=num的代码语句存在位置问题。后来看了下代码还是自己没有考虑清楚。这种类型的题目就是要想清楚你的做法,以及边界条件。classSolution{public:......
  • Nginx配置静态代理/静态资源映射时root与alias的区别,带前缀映射用alias
    场景Nginx搭建静态资源映射实现远程访问服务器上的图片资源:https://blog.csdn.net/BADAO_LIUMANG_QIZHI/article/details/117283572以上在配置静态资源映射时使用的如下配置     location/{           root  D:/pic_old/;           try_......
  • 前缀和与差分数组
    目录一维前缀和二维前缀和差分数组差分数组反推出原始数组差分数组模板前缀和应用场景:原始数组不会被修改的情况下,频繁查询某个区间的累加和。eg:计算数组下标2到5的数组和,原本用for循环,有了前缀和直接用5的前缀和减去2的前缀和得到答案,可以将O(n)的复杂度降为O(1)一维前缀和......
  • 前缀和算法讲解(二)
    首先,大家看一下一维的前缀和:https://blog.csdn.net/hjyowl/article/details/136580832?spm=1001.2014.3001.5502今天,我们讲解一下二维的前缀和.先看题:输入一个 n 行 m 列的整数矩阵,再输入 q 个询问,每个询问包含四个整数 x1,y1,x2,y2,表示一个子矩阵的左上角坐标和右下......
  • 蓝桥杯算法基础(29)字符串匹配(RabinKarp)(KMP)(前缀树,字典树,trie,后缀数组,高度数组)
     RabinKarpRabinKarpS:ABABABm个P:ABBn个1.朴素算法,挨个匹配2.哈希法hash->滚动哈希c0*31^2+c1*31^1+c2类似于进制的求法求hash值(c0*31+c1)*31+c2hash(p)=o(n)hash(s)=o(m*n)privatestaticvoidmatch(Stringp,Strings){longhash_p=hash(p);......