前缀树

前缀树又称为字典树，接触这个数据结构是因为在 LeetCode 上面刷到这道题 14. Longest Common Prefix。然后，我去看了下官方推荐的文章以及其他人的博客，基本上是可以理解这种数据结构的吧！
下面就贴下这种数据结构的一种实现的代码吧：
节点类：

package ds;

/**
 * Created by clearbug on 2018/3/6.
 *
 * 字典树节点类
 */
public class TrieNode {

    // R links to node children
    private TrieNode[] links;

    private final int R = 26;

    private boolean isEnd;

    // number of children non null links
    private int size;

    public TrieNode() {
        links = new TrieNode[R];
    }

    public boolean containsKey(char ch) {
        return links[ch - 'a'] != null;
    }

    public TrieNode get(char ch) {
        return links[ch - 'a'];
    }

    public void put(char ch, TrieNode node) {
        links[ch - 'a'] = node;
        size++;
    }

    public int getLinks() {
        return size;
    }

    public void setEnd() {
        isEnd = true;
    }

    public boolean isEnd() {
        return isEnd;
    }

}

字典树类：

package ds;

/**
 * Created by clearbug on 2018/3/6.
 *
 * 字典树
 */
public class Trie {

    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    // Inserts a word into the trie.
    public void insert(String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            char currentChar = word.charAt(i);
            if (!node.containsKey(currentChar)) {
                node.put(currentChar, new TrieNode());
            }
            node = node.get(currentChar);
        }
        node.setEnd();
    }

    // search a prefix or whole key in trie and returns the node where search ends
    private TrieNode searchPrefix(String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            char curLetter = word.charAt(i);
            if (node.containsKey(curLetter)) {
                node = node.get(curLetter);
            } else {
                return null;
            }
        }
        return node;
    }

    // Returns if the word is in the trie.
    public boolean search(String word) {
        TrieNode node = searchPrefix(word);
        return node != null && node.isEnd();
    }

    // Returns is there is any word in the trie that starts with the given prefix.
    public boolean startsWith(String prefix) {
        TrieNode node = searchPrefix(prefix);
        return node != null;
    }

    // just for https://leetcode.com/problems/longest-common-prefix/description/
    private String searchLongestPrefix(String word) {
        TrieNode node = root;
        StringBuilder prefix = new StringBuilder();
        for (int i = 0; i < word.length(); i++) {
            char curLetter = word.charAt(i);
            if (node.containsKey(curLetter) && (node.getLinks() == 1) && (!node.isEnd())) {
                prefix.append(curLetter);
                node = node.get(curLetter);
            } else {
                return prefix.toString();
            }
        }
        return prefix.toString();
    }

}

测试一把：

import ds.Trie;

/**
 * Created by clearbug on 2018/3/6.
 */
public class Test {

    public static void main(String[] args) {
        String[] words = {"are", "you", "ok"};
        String[] words2 = {"yes", "no"};

        Trie trie = new Trie();
        for (int i = 0; i < words.length; i++) {
            trie.insert(words[i]);
        }

        for (int i = 0; i < words.length; i++) {
            System.out.println("Search "" + words[i] + "" result: " + trie.search(words[i]));
        }
        for (int i = 0; i < words2.length; i++) {
            System.out.println("Search "" + words2[i] + "" result: " + trie.search(words2[i]));
        }
    }
}

运行结果：

Search "are" result: true
Search "you" result: true
Search "ok" result: true
Search "yes" result: false
Search "no" result: false

参考

https://leetcode.com/articles/implement-trie-prefix-tree/
https://www.cnblogs.com/grandyang/p/4491665.html