题目描述

解题思路

前缀树的介绍
前缀树就是每一层都是比上一层多一个字母，没搜索一层，都是不同的前缀，但是使用了一个isEnd字段来表示该节点是否已经到了尾部，此时就不是前缀了，而是整个单词。（26子节点也是有hash映射的关系，所以根据字母很好定位在哪个子节点）

所以搜索的时候每层进行搜索，hash表定位子节点是否存在，再继续搜索，直到整个单词搜索完后都没有遇到null节点，表示前面的字符都出现了。
但是search函数搜索完之后需要检验isEnd是否为true，防止此整个单词不是整个单词而是别人的前缀字符串。

// 前缀树实现
class Trie {
    class TrieNode {
        boolean isEnd = false;
        TrieNode[] next;
        public TrieNode() {
            this.isEnd = false;
            this.next = new TrieNode[26];
        }
    }
    TrieNode root;
    public Trie() {
        root = new TrieNode();
    }
    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            // 如果前缀数没有构造过，那么就生成节点
            if (node.next[c - 'a'] == null) {
                node.next[c - 'a'] = new TrieNode();
            }
            // 移动到映射的节点继续构造
            node = node.next[c - 'a'];
        }
        // 整个单词构造完成之后，设置该节点isEnd为true
        node.isEnd = true;
    }
    public boolean search(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            // 中间就匹配不了了，所以匹配不到最后节点
            if (node.next[c - 'a'] == null) {
                return false;
            }
            node = node.next[c - 'a'];
        }
        // word前面都匹配完了，如果最后一个节点isEnd是true，那么表示出现过该单词，而不是前缀
        return node.isEnd;
    }
    public boolean startsWith(String prefix) {
        TrieNode node = root;
        for (char c : prefix.toCharArray()) {
            // 中间就匹配不了了，所以匹配不到最后节点
            if (node.next[c - 'a'] == null) {
                return false;
            }
            node = node.next[c - 'a'];
        }
        // 不用管是否是最后一个单词，只要前面都匹配，就满足前缀
        return true;
    }
}

自己瞎搞的，还过了…

class Trie {
    Set<String> trieSet;
    Set<String> preSet;
    public Trie() {
        trieSet = new HashSet<>();
        preSet = new HashSet<>();
    }
    public void insert(String word) {
        for (int i = 0; i < word.length() - 1; i++) {
            preSet.add(word.substring(0, i + 1));
        }
        trieSet.add(word);
    }
    public boolean search(String word) {
        return trieSet.contains(word);
    }
    public boolean startsWith(String prefix) {
        return preSet.contains(prefix);
    }
}