LeetcodeT208-字典树Trie

跟前两天的KMP算法一样，字典树也是用来解决字符串查找类的问题。KMP解决的是单条字符串在模式串中是否存在的问题。而字典树就跟名字一样，查看在一堆的单词中查找某个字符串是否存在。回忆下手动查字典的过程，比如查找apple。首先在目录找到A开头的单词在哪一页，然后按顺序（a-z即字典序）定位到p，重复过程最终定位到结果。

1. 首先需要一个建树的过程，二叉树都很熟悉，有左节点右节点，字典树也差不多，它有着26个子节点（a-z下标就从0-25），甚至存在大小写混合的情况，完全可以有52个子节点。

2. 插入字符，插入a这个字符，就在当前节点的a[0]处初始化一个节点，作为存在这条路径存在的判断。接着以a[0]这个节点作为当前节点，继续往下创建（循环或者递归都可）。直到完成apple的插入。

   
   trie.png
   

   3.搜索单词，搜索的流程与插入类似，插入的过程是如果没有该节点就创建，搜索时没有就说明单词不存在。还有一种情况，如果已经插入了apple这个单词，但是我们搜的是app。能够沿着路径找到，但是不代表字典中就存在app这个单词，所以需要增加一个end标记，在单词的最后一个字符创建完成后设置end为true，代表这是一个完整的单词。

接下来看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 构成的。
// 保证所有输入均为非空字符串。
//
// Related Topics 设计 字典树

附代码

private static class Trie {

    //俗称字典树，可以看成是26叉树，每个叉表示a-z对应的字母
    Trie[] son;
    boolean end;

    /**
     * Initialize your data structure here.
     */
    public Trie() {
        son = new Trie[26];
    }

    /**
     * Inserts a word into the trie.
     */
    public void insert(String word) {
        char[] ch = word.toCharArray();
        Trie root = this;
        for (int i = 0; i < ch.length; i++) {
            if (root.son[ch[i] - 'a'] == null) {
                root.son[ch[i] - 'a'] = new Trie();
            }
            root = root.son[ch[i] - 'a'];
        }
        //标记为单词末尾
        root.end = true;
    }

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

    /**
     * Returns if there is any word in the trie that starts with the given prefix.
     */
    public boolean startsWith(String prefix) {
        char[] ch = prefix.toCharArray();
        Trie root = this;
        for (int i = 0; i < ch.length; i++) {
            if (root.son[ch[i] - 'a'] == null) {
                return false;
            }
            root = root.son[ch[i] - 'a'];
        }
        for (int i = 0; i < 26; i++) {
            if (son[ch[i] - 'a'] != null) {
                return true;
            }
        }
        return false;
    }
}