背景

字典树，又称前缀树（英文名：Trie Tree），为 Edward Fredkin 发明。

举个例子，给出一些单词，（and，as，at，cn，com），则其字典树如下：

从上图可以发现，它有 3 个基本性质：

1）根结点不包含字符，除根结点外每一个结点都只包含一个字符。
2）从根结点到某一结点，路径上经过的字符连接起来，为该结点对应的字符串。
3）每个结点的所有子结点包含的字符都不相同。

字典树是一个很重要的数据结构，其主要应用为：

1）词频统计：例如，给定一个由 10 万个单词组成的库，现要你判断一个单词是否有在库中出现，若出现，求出共出现多少次。
2）前缀匹配：以上图为例，如果想获取所有以 "a" 开头的字符串，那么从图中可以很明显的看到是：（and，as，at）。因此利用这个特性，可以巧妙地实现搜索提示功能，如输入一个网址，可以自动列出可能的选择。当没有完全匹配的搜索结果，可以列出前缀最相似的可能。

Java 实现

import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class TrieTree {
    private Node root = new Node();

    public void putAll(String... words) {
        putAll(Arrays.asList(words));
    }

    public void putAll(List<String> words) {
        words.stream().forEach(this::put);
    }

    public void put(String word) {
        Node node = root;
        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            Node next = node.addNextIfAbsent(ch);
            node = next;
        }
        node.markEnd();
    }

    public boolean contains(String text) {
        for (int i = 0; i < text.length(); ++ i) {
            if (contains(text, i, text.length())) {
                return true;
            }
        }
        return false;
    }

    private boolean contains(String word, int left, int right) {
        Node node = root;
        for (int i = left; i < right; i++) {
            char ch = word.charAt(i);
            Node next = node.findNext(ch);

            if (next == null) {
                return false;
            }
            if (next.isEnd()) {
                return true;
            }

            node = next;
        }
        return false;
    }

    private static class Node {
        private Map<Character, Node> children;
        private boolean end;

        public Node() {
            children = new HashMap<>();
            end = false;
        }

        public Node findNext(char ch) {
            return this.children.get(ch);
        }

        public Node addNextIfAbsent(char ch) {
            Node next = findNext(ch);
            if (next == null) {
                next = new Node();
                this.children.put(ch, next);
            }
            return next;
        }

        public boolean isEnd() {
            return this.end;
        }

        public void markEnd() {
            this.end = true;
        }
    }
}

测试

public class TrieDemo {
    public static void main(String[] args) {
        TrieTree trieTree = new TrieTree();
        trieTree.putAll("素人", "huhu");

        System.out.println(trieTree.contains("aaa素人bbb")); // true
        System.out.println(trieTree.contains("aaabbb")); // false
    }
}