题目链接

英文链接：https://leetcode.com/problems/implement-trie-prefix-tree/

中文链接：https://leetcode-cn.com/problems/implement-trie-prefix-tree/

题目详述

实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。

示例:

Trie trie = new Trie();

trie.insert("apple");
trie.search("apple");   // 返回 true
trie.search("app");     // 返回 false
trie.startsWith("app"); // 返回 true
trie.insert("app");   
trie.search("app");     // 返回 true

说明:

你可以假设所有的输入都是由小写字母 a-z 构成的。
保证所有输入均为非空字符串。

题目详解

新建一个结点结构，用它来构造26叉树。
注意 search 和 startsWith 的区别与联系。
二者都是在字典树中存在，但 search 多一个限制条件：需要满足是一个单词。
故可以提取出一个公共方法 searchPrefix。

public class LeetCode_00208 {

    class Trie {
        private class Node {
            Node[] next = new Node[26];
            boolean isEnd = false;
        }

        private Node root;

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

        public void insert(String word) {
            Node node = root;
            for (char c : word.toCharArray()) {
                int index = c - 'a';
                if (node.next[index] == null) {
                    node.next[index] = new Node();
                }
                node = node.next[index];
            }
            node.isEnd = true;
        }

        public boolean search(String word) {
            Node node = searchPrefix(word);
            return node != null && node.isEnd;
        }

        public boolean startsWith(String prefix) {
            return searchPrefix(prefix) != null;
        }

        private Node searchPrefix(String prefix) {
            Node node = root;
            for (char c : prefix.toCharArray()) {
                int index = c - 'a';
                if (node.next[index] == null) {
                    return null;
                }
                node = node.next[index];
            }
            return node;
        }
    }
}