LeetCode刷题实战208：实现 Trie (前缀树)-技术圈

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做 实现 Trie (前缀树)，我们先来看题面：

https://leetcode-cn.com/problems/implement-trie-prefix-tree/

Trie (we pronounce "try") or prefix tree is a tree data structure used to retrieve a key in a strings dataset. There are various applications of this very efficient data structure, such as autocomplete and spellchecker.

题意

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

解题

https://segmentfault.com/a/1190000015804960

思路分析：

树是由节点组成，节点定义应该包含节点值(前缀树的定义，值应该为一个字符char)和叶子节点的指针，但是为了识别是否为一个单词的最后一个字符，所以增加一个boolean变量识别。

由于已知输入为全小写(a-z)的字母，所以可以使用一个长度为26的数组存储叶子节点。且由于a-z的ASCII码是连续的，其ASCII是从97-123，所以可以直接使用 ASCII码-97=对应节点的数组下标。

class Trie {
    /**
     * 当前节点的值
     */
    public char value;
    /**
     * a-z有26个字母，需要访问时由于a的ASCII码为97，所以所有字母访问的对应下表皆为 字母的ASCII码-97
     */
    public Trie[] children=new Trie[26];
    /**
     * 标识此节点是否为某个单词的结束节点
     */
    public boolean endAsWord=false;
    
    public Trie() {
        
    }
    /**
     * 插入一个单词
     * @param word 单词
     */
    public void insert(String word) {
        if(word!=null){
            //分解成字符数组
            char[] charArr=word.toCharArray();
            //模拟指针操作,记录当前访问到的树的节点
            Trie currentNode=this;
            for(int i=0;i<charArr.length;i++){
                char currentChar=charArr[i];
                //根据字符获取对应的子节点
                Trie node=currentNode.children[currentChar-97];
                if(node!=null && node.value==currentChar){//判断节点是否存在
                   currentNode=node;
                }else{//不存在则创建一个新的叶子节点,并指向当前的叶子节点
                    node=new Trie();
                    node.value=currentChar;
                    currentNode.children[currentChar-97]=node;
                    currentNode=node;
                }
            }
            //这个标识很重要
            currentNode.endAsWord=true;
        }
    }
    /**
     * 检索指定单词是否在树中
     * @param word 单词
     */
    public boolean search(String word) {
        boolean result=true;
        if(word!=null && !word.trim().equals("")){
            char[] prefixChar=word.toCharArray();
            Trie currentNode=this;
            for(int i=0;i<prefixChar.length;i++){
                char currentChar=prefixChar[i];
                Trie node=currentNode.children[currentChar-97];
                if(node!=null && node.value==currentChar){//判断节点是否存在
                   currentNode=node;
                }else{
                    result=false;
                    break;
                }
            }
            if(result){
                result=currentNode.endAsWord;
            }
        }
        return result;
    }
    /**
     * 检索指定前缀是否在树中
     * @param word 单词
     */
    public boolean startsWith(String prefix) {
        boolean result=true;
        if(prefix!=null && !prefix.trim().equals("")){
            char[] prefixChar=prefix.toCharArray();
            Trie currentNode=this;
            for(int i=0;i<prefixChar.length;i++){
                char currentChar=prefixChar[i];
                Trie node=currentNode.children[currentChar-97];
                if(node!=null && node.value==currentChar){//判断节点是否存在
                    currentNode=node;
                }else{
                    result=false;
                    break;
                }
            }
        }
        return result;
    }
}