前言

前缀树，前缀树，顾名思义，就是一颗前缀的树，呸，全是废话，话说有二叉树，多叉树，平衡树，B+树，嘿，这又来一个前缀树，既然来了，咱们就是干！

介绍

前缀，英文Trie，俗称字典树，哦！字典，字典用来干嘛的，用来查字的哈，所以，这棵树的主要算法作用就是做快速的查找某个单词或者字符前缀的数据结构，但是这种东西吧，其实在工程领域，也就是在公司内实际做业务开发的过程中是使用不到这种东西的，但是在算法领域，却是很常见的一个数据结构，在工程领域大多情况下，都是一个HashMap，来存对应的东西就够了.

我对于前缀树的理解吧，就是第一个节点是不存东西的，其余每一个节点都用下标来计算这是对应的26位字母中的哪一个，所以对应了数据结构如下

class Node{
	Node[] nexts;
	boolean isEnd;
}

来表明这个单词是否已经到了最后，用一个布尔类型的isEnd来表示

这里用LeetCode-211. 添加与搜索单词 - 数据结构设计

来对前缀树做练习

请你设计一个数据结构，支持 添加新单词 和 查找字符串是否与任何先前添加的字符串匹配 。

实现词典类 WordDictionary ：

1. WordDictionary() 初始化词典对象
2. void addWord(word) 将 word 添加到数据结构中，之后可以对它进行匹配
3. bool search(word) 如果数据结构中存在字符串与 word 匹配，则返回 true ；否则，返回  false 。word 中可能包含一些 '.' ，每个 . 都可以表示任何一个字母。

**输入**：
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
输出：
[null,null,null,null,false,true,true,true]

**解释**：
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad"); // return False
wordDictionary.search("bad"); // return True
wordDictionary.search(".ad"); // return True
wordDictionary.search("b.."); // return True

如下是自己对于这道题的一种题解

class WordDictionary {
    
    Node root;

    public WordDictionary() {
        root = new Node();
    }
    
    public void addWord(String word) {
        Node node = root;

        for(int i = 0;i < word.length(); i++){
            int index = word.charAt(i) - 'a';
            if(node.nexts[index] == null){
                node.nexts[index] = new Node();
            }
            node = node.nexts[index];
        }

        node.isEnd = true;
    }
    
    public boolean search(String word) {
        return search(word, root, 0);
    }

    public boolean search(String word, Node node, int i){
        if(node == null) {
            return false;
        }
        if(i >= word.length()){
            return node.isEnd;
        }

        char c = word.charAt(i);
        if(c == '.'){
            for (Node next : node.nexts) {
                if (search(word, next, i + 1)) {
                    return true;
                }
            }
            return false;
        }else{
            return search(word, node.nexts[c - 'a'], i+1);
        }
    }

    class Node{
        Node[] nexts = new Node[26];
        boolean isEnd = false;
    }
}

当然我自己最拿到这道题的时候，是没有直接使用前缀树的，其实是对于这种题的敏感度不是很好， 我第一道题直接使用了一个HashMap，key来存单词的长度，value是一个String的List，来存对应长度的所有单词，然后要查找单词的时候，就先用长度拿到对应的List，然后一个一个拿出来进行对比，碰到 . 就跳过，比较下一个，如果这个单词能匹配完，就返回true，说明存在要查找的单词

class WordDictionary {
    Map<Integer, List<String>> map;

    public WordDictionary() {
        map = new HashMap<>();
    }
    
    public void addWord(String word) {
        if(map.containsKey(word.length())){
            List<String> list = map.get(word.length());
            if(!list.contains(word)){
                list.add(word);
            }
        }else{
            List<String> list = new ArrayList<String>();
            list.add(word);
            map.put(word.length(), list);
        }
    }
    
    public boolean search(String word) {
        //怎么快速的模糊查找 好比Mysql中的模糊查找 是如何实现的？
        //哦！  .的就不用管  相当于全扫描
        int length = word.length();
        if(!map.containsKey(length)){
            return false;
        }

        List<String> list = map.get(length);
        for(String s : list){
            char[] chars = s.toCharArray();
            char[] cmpChars = word.toCharArray();
            boolean flag = true;
            for(int i = 0; i < chars.length; i++){
                if(cmpChars[i] == '.'){
                    continue;
                }
                if(cmpChars[i] != chars[i]){
                    flag = false;
                    break;
                }
            }
            if(flag){
                return true;
            }
        }
        return false;
         
    }
}