leetcode208. 实现 Trie (前缀树)

小灰灰 2023-07-03 08:20 2阅读 0赞

实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。

示例:

Trie trie = new Trie();

trie.insert("apple");  
trie.search("apple"); // 返回 true  
trie.search("app"); // 返回 false  
trie.startsWith("app"); // 返回 true  
trie.insert("app");  
trie.search("app"); // 返回 true  
说明:

你可以假设所有的输入都是由小写字母 a-z 构成的。  
保证所有输入均为非空字符串。

[前缀树介绍][Link 1]

public class Trie {
        private boolean is_string=false;
        private Trie next[]=new Trie[26];
    
        public Trie(){}
    
        public void insert(String word){//插入单词
            Trie root=this;
            char w[]=word.toCharArray();
            for(int i=0;i<w.length;++i){
                if(root.next[w[i]-'a']==null)root.next[w[i]-'a']=new Trie();
                root=root.next[w[i]-'a'];
            }
            root.is_string=true;
        }
    
        public boolean search(String word){//查找单词
            Trie root=this;
            char w[]=word.toCharArray();
            for(int i=0;i<w.length;++i){
                if(root.next[w[i]-'a']==null)return false;
                root=root.next[w[i]-'a'];
            }
            return root.is_string;
        }
        
        public boolean startsWith(String prefix){//查找前缀
            Trie root=this;
            char p[]=prefix.toCharArray();
            for(int i=0;i<p.length;++i){
                if(root.next[p[i]-'a']==null)return false;
                root=root.next[p[i]-'a'];
            }
            return true;
        }
    }

[Link 1]: https://blog.csdn.net/hebtu666/article/details/83141560

发表评论取消回复

表情：

评论列表（有 0 条评论，2人围观）

还没有评论，来说两句吧...

相关阅读

相关 208. 实现 Trie (前缀树)

题目Trie（发音类似 “try”）或者说前缀树是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。请...

旧城等待，/ 2024年05月08日 06:22/ 0 赞/ 87 阅读

相关 leetcode208. 实现 Trie (前缀树)

实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。示例: Trie trie = new Trie(); tr

小灰灰/ 2023年07月03日 08:20/ 0 赞/ 3 阅读

相关 208. 实现 Trie (前缀树)

题目： [208. 实现 Trie (前缀树)][208. _ Trie] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpd

太过爱你忘了你带给我的痛/ 2023年02月23日 14:28/ 0 赞/ 27 阅读

相关 208. 实现 Trie (前缀树)（JS实现）

1 题目 > 实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。 > 示例: > Trie trie =

小灰灰/ 2022年11月25日 13:06/ 0 赞/ 141 阅读

相关 Leetcode208. 实现 Trie (前缀树)

前言蒟蒻做题。已有工作字典树又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常

向右看齐/ 2022年11月19日 04:28/ 0 赞/ 204 阅读

相关 LeetCode 208. 实现 Trie (前缀树)

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

痛定思痛。/ 2022年10月29日 13:30/ 0 赞/ 180 阅读

相关 208. 实现 Trie (前缀树)

> 请你实现 Trie 类： > > Trie() 初始化前缀树对象。 > void insert(String word) 向前缀树中插入字符串 word 。 >

- 日理万妓/ 2022年10月12日 12:09/ 0 赞/ 199 阅读

相关 leetcode 208. Implement Trie (Prefix Tree) | 208. 实现 Trie 前缀树（Java）

题目 [https://leetcode.com/problems/implement-trie-prefix-tree/][https_leetcode.com_pro

绝地灬酷狼/ 2022年10月06日 00:35/ 0 赞/ 171 阅读

相关 leetcode 208. 实现 Trie (前缀树)

实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。示例: Trie trie = new Trie();

淡淡的烟草味﹌/ 2022年02月22日 01:41/ 0 赞/ 247 阅读

相关 leetcode：208. 实现 Trie (前缀树)

实现一个 Trie (前缀树)，包含 `insert`, `search`, 和 `startsWith` 这三个操作。示例: Trie trie = new T

水深无声/ 2021年09月28日 11:16/ 0 赞/ 336 阅读