分类

树 > 多叉树 ， 中等难度

为什么容易被选为面试题

1、前缀树的实现并不难，但有很多编码细节。“不难+多细节”是面试热点。

2、二叉树学校教了很多，但是多叉树的实现在学校课程上是没有做过的

题目

Trie树，或者说前缀树，是一种树形数据结构，用于……应用情景如“自动补全”和“拼写检查”。实现功能：

• 插入：void insert(String word)
• 搜索完整字符串：boolean search(String word)
• 搜索前缀：boolean startsWith(String prefix)

示例：

Trie trie = new Trie();trie.insert("apple");trie.search("apple");   // 返回 Truetrie.search("app");     // 返回 Falsetrie.startsWith("app"); // 返回 Truetrie.insert("app");trie.search("app");     // 返回 True

要求：

• 1 <= word.length, prefix.length <= 2000
• word 和 prefix 仅由小写英文字母组成
• insert、search 和 startsWith 调用次数 总计 不超过 3 * 104 次

考点

这个要求可以说很宽裕了，考察的并不是极致的性能，而是逻辑和细节。

1、遍历字符串。遍历字符串是一个很基础的功能，但是工作中很少有这种操作。

2、null值判断。输入值可能为null。

3、判前缀和判完整是不一样的，前缀字符串只需要遍历到即可，完整字符串需要遍历到且后面没有其他字符了。

4、插入的完整字符串末尾需要有个标记。可以看到sample里面，insert apple之后，搜索app是搜不到的，但是在insert app之后，搜索app就能搜到了。

我的第一版代码

我的代码比较丑陋，但实现了基本功能。比如“判断末尾”，我当时看到输入的只会有英文字母，所以用了特殊字符，而官方的解答则是增加一个“boolean isEnd”变量，而且用的是数组，会比这个来得更精巧。

class Trie {    private Node root;    public Trie() {        root = new Node();    }        public void insert(String word) {        if (word == null) {            return;        }        Node p = root;        for (int i = 0; i < word.length(); i++) {            char ch = word.charAt(i);            p.insert(ch);            p = p.nextNode(ch);        }        p.insert('-');    }        public boolean search(String word) {        if (word == null) {            return false;        }        Node p = root;        for (int i = 0; i < word.length(); i++) {            char ch = word.charAt(i);            if (p == null || !p.contains(ch)) {                return false;            }            p = p.nextNode(ch);        }        return p == null || p.isEnd();    }        public boolean startsWith(String prefix) {        if (prefix == null) {            return false;        }        Node p = root;        for (int i = 0; i < prefix.length(); i++) {            char ch = prefix.charAt(i);            if (p == null || !p.contains(ch)) {                return false;            }            p = p.nextNode(ch);        }        return true;    }    public static class Node {        private Map<String, Node> next;        public void insert(char ch) {            if (this.next == null) {                this.next = new HashMap<>();            }            this.next.putIfAbsent(String.valueOf(ch), new Node());        }        public boolean contains(char ch) {            if (this.next == null) {                return false;            }            return this.next.containsKey(String.valueOf(ch));        }        public Node nextNode(char ch) {            if (this.next == null) {                return null;            }            return this.next.get(String.valueOf(ch));        }        public boolean isEnd() {            return this.contains('-');        }    }}

如果觉得有收获，就收藏转发一下吧，谢谢。