基础理论

什么是字典树

为了能够快速的找到一个单词，大佬们提出了一个用空间换时间的数据结构用来存储单词。具体表现为

图解

比如 我们如何存储but 和 cat 两个单词。

首先我们确定每一个节点：里面有isEnd 和一个指向子节点的数组。长为26（26个字母）。对于每一个字母，如果有单词对应这个字母，就存储一个树节点。否则为空。

典型的字典树运用场景

单词推导， 输入you 自动推导youtube，

代码实现

Tried 的存储结构 树结构boolean isEnd()TreeNode[] children // 一个字母表26长度的数组，如果第i位存在字母，则，下一个字母可以为'a'+i;

Treid 字典树的基本原子操作

构造一个TreeNode 点

public TreeNode() { children = new TreeNode[26];}

判断当前是否包含某这个字母

public boolean containsKey(char ch) { return children[ch - 'a'] != null; }在当前节点 获取char ch，也就是说或者当前节点的字母

public char get(char ch) { return children[ch - 'a']}

在当前节点插入一个node

public void put(char ch, TreeNode node) { children[ch - 'a'] = node; }

将当前点设为终点

public void setEnd() { isEnd = true;}判断当前Node 是不是endpublic boolean isEnd() {return isEnd;}

Tried树的常用操作

增加单词 见代码

查找单词 见代码

查找满足某一给前缀的所有单词 见代码

class Trie {

    class TreeNode{
        private boolean isEnd = false;
        private final int R = 26;
        TreeNode[] children;

        public TreeNode() {
            children = new TreeNode[R];
        }

        public TreeNode get(char ch) {
            return children[ch - 'a'];
        }

        public void put(char ch, TreeNode node) {
            children[ch - 'a'] = node;
        }

        public void setEnd() {
            isEnd = true;
        }

        public boolean isEnd() {
            return isEnd;
        }

    }

    private TreeNode root;
    /** Initialize your data structure here. */
    public Trie() {
        root = new TreeNode();
    }
    
    /** Inserts a word into the trie. */
    public void insert(String word) {
        TreeNode temp = root;
        for (int i = 0; i < word.length() ; i++) {
            char ch = word.charAt(i);
            if (temp.get(ch) == null) {
                TreeNode chNode = new TreeNode();
                temp.put(ch, chNode);
            }
            temp = temp.get(ch);
        }
        temp.setEnd();
    }
    
    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        TreeNode temp = root;
        for (int i = 0; i < word.length() ; i++) {
            char ch = word.charAt(i);
            if (temp.get(ch) == null) {
                return false;
            }
            temp = temp.get(ch);
        }
        // 对于 dad 和 daddy 怎么存的 dad 的isEnd 是什么
        // 按照我这种方法dad 的isEnd 是false
        // 那就和下面的寻找前缀没有区别了
        if(temp.isEnd() == true) {
            return true;
        } else {
            return false;
        }
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        TreeNode temp = root;
        for (int i = 0; i < prefix.length() ; i++) {
            char ch = prefix.charAt(i);
            if (temp.get(ch) == null) {
                return false;
            }
            temp = temp.get(ch);
        }
        // 对于 dad 和 daddy 怎么存的 dad 的isEnd 是什么
        // 按照我这种方法dad 的isEnd 是false
        return true;
    }
}

思维导图