leetcode之208-实现 Trie (前缀树)

今天立冬，祝大家立冬快乐哦！

1

在上篇文章（传送门）中，我们已经详细介绍并用两种数据结构实现了 Trie。实际上把上篇文章中的任何一版代码提交给 leetcode 都完全可以解答本题，所以本文的意义并不在于如何解答这道题。

写 java 的人，肯定都知道，面向对象的三大特征：封装、继承、多态。而本文就是我从官方题解中得到的一点点关于「封装」的体会，做个小小的分享。

问题

先回顾一下我们上篇文章中的代码，其实对于 Node 的封装做得并不好，可以说几乎就没有封装。问题如以下两点：

1. 出于封装性和安全性的考虑，对于 Node 的两个成员变量，我们不应该直接访问，而应该通过成员方法去访问。

因为，首先，将成员变量设置为 public 权限，对于该成员变量的访问和修改的控制就不再由封装它的对象来控制，而是由调用它的类来控制，这样就破坏了 java 面向对象的封装性；其次，程序何时何地修改成员变量的值也很难控制和排查，从而影响安全性。

2. 假如我们想达到这个目的：随意切换底层数据结构（比如从数组切换到 Map，或反之），但是不想影响到原本已经实现的代码功能。

如果要用上篇文章中的代码实现这个目的，那么大多数方法都需要修改一些实现细节。比如判断当前节点是否包含指向下一个字符的指针，获取下一个节点，往当前节点之后插入一个节点等。

修改的地方越多，出问题的概率就越大。最好能做到上层代码尽量不要动，这样的改动才是最放心的。

所以，我们可以把这些操作细节抽象出来，在 Node 中做一些封装，提供给上层代码使用。

对 Node 进行封装

/**
 * 抽象类，可作为具体数据结构实现的父类
 */
public abstract class Node {

    /**
     * 该节点是否是字符串的结尾
     */
    protected boolean isEndingChar;

    protected void setEndingChar() {
        isEndingChar = true;
    }

    protected boolean isEndingChar() {
        return isEndingChar;
    }

    protected boolean notContainsKey(char c) {
        return !this.containsKey(c);
    }

    /**
     * 当前节点是否包含指向下一个字符的指针
     */
    abstract boolean containsKey(char c);

    /**
     * 获取下一个节点
     */
    abstract Node get(char c);

    /**
     * 往当前节点之后插入一个节点
     */
    abstract void put(char c);
}

/**
 * 数组实现
 */
public class ArrayTrieNode extends Node {

    /**
     * 指向后续节点的指针
     */
    private final ArrayTrieNode[] next;

    private ArrayTrieNode(boolean isEndingChar) {
        this.isEndingChar = isEndingChar;
        next = new ArrayTrieNode[26];
    }

    public ArrayTrieNode() {
        this(false);
    }

    @Override
    public boolean containsKey(char c) {
        return next[c - 'a'] != null;
    }

    @Override
    public Node get(char c) {
        return next[c - 'a'];
    }

    @Override
    public void put(char c) {
        next[c - 'a'] = new ArrayTrieNode();
    }
}

/**
 * HashMap 实现
 */
public class HashMapTrieNode extends Node {

    /**
     * 指向后续节点的指针
     */
    private final Map<Character, HashMapTrieNode> next;

    private HashMapTrieNode(boolean isEndingChar) {
        this.isEndingChar = isEndingChar;
        next = new HashMap<>();
    }

    public HashMapTrieNode() {
        this(false);
    }

    @Override
    public boolean containsKey(char c) {
        return next.containsKey(c);
    }

    @Override
    public Node get(char c) {
        return next.get(c);
    }

    @Override
    public void put(char c) {
        next.put(c, new HashMapTrieNode());
    }
}

上层代码

/**
 * Implement Trie (Prefix Tree)
 * 实现 Trie（前缀树）
 */
public class Trie {

    /**
     * The root node.
     */
    private final Node root;

    /**
     * Initialize the data structure.
     */
    public Trie() {
        // 修改处
        root = new ArrayTrieNode();
        // root = new HashMapTrieNode();
    }

    /**
     * Inserts a word into the trie.
     */
    public void insert(String word) {
        Node node = root;
        for (int i = 0; i < word.length(); i++) {
            char curLetter = word.charAt(i);
            if (node.notContainsKey(curLetter)) {
                node.put(curLetter);
            }
            node = node.get(curLetter);
        }
        node.setEndingChar();
    }

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

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

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

通过对 Node 节点的封装，当需要切换底层数据结构时，只需要在 Trie 构造方法中初始化不同的底层数据结构实现即可，其它代码我们一行都不需要修改！

通过两篇文章的代码对比，可以看到，通过良好的封装，可以使代码的可读性大大提高，而且底层数据结构的变更完全不会给上层代码带来影响，这会带来不错的体验。

---