LeetCode解析------208.实现 Trie (前缀树)-字典树

题目：

实现一个 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 构成的。 保证所有输入均为非空字符串。

简单介绍： 题目：实现Trie（前缀树） 题目难度：中等 使用语言：JAVA 这道题来自leetcode题库的字典树标签。

解题思路： 首先看题、分析题意，我们可以明确1个关键点： 1.前缀树究竟是什么？ （含义： 前缀树一般指字典树。又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。 性质： 根节点不包含字符，除根节点外每一个节点都只包含一个字符； 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串； 每个节点的所有子节点包含的字符都不相同。） 既然，我们已经分析出来题目的关键任务了，下面我们就可以开始思考实现了。 我们采用算法与数据结构的思路来剖析一下这题

数据结构： 要实现对数据的操作，我们要先明确存储数据的数据结构。 该题的数据结构的作用： 1.Trie来保存单词的一个字符

算法： 既然明确了我们的数据结构，我们就可以开始我们的算法分析了。 1.第一步，初始化工作（为保存字符申请空间）。 2.第二步，编写各个函数。

代码部分：

public class Trie {
          
   
    boolean isString=false;
    Trie next[];


    public Trie() {
          
   
        next=new Trie[26];
    }

    /** 插入单词，有则往下，无则开辟结点 */
    public void insert(String word) {
          
   
        Trie root=this;
        for(int i=0;i<word.length();i++){
          
   
            if(root.next[word.charAt(i)-a]==null)
                root.next[word.charAt(i)-a]=new Trie();

            root=root.next[word.charAt(i)-a];
        }
        root.isString=true;
    }

    /** Returns if the word is in the trie. */
    public boolean search(String word) {
          
   
        Trie root=this;
        for(int i=0;i<word.length();i++){
          
   
            if(root.next[word.charAt(i)-a]==null)
                return false;

            root=root.next[word.charAt(i)-a];
        }
        return root.isString;

    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
          
   
        Trie root=this;
        for(int i=0;i<prefix.length();i++){
          
   
            if(root.next[prefix.charAt(i)-a]==null)
                return false;

            root=root.next[prefix.charAt(i)-a];
        }
        return true;


    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */

时间、空间复杂度：

结语： 晚安！晚安！晚安！晚安！晚安！晚安！晚安！晚安！晚安！晚安！晚安！