本文共 1455 字，大约阅读时间需要 4 分钟。

链接：

大意：

实现前缀树（也称为字典树）。规定：所有输入字符串的字符为'a' - 'z'。例子：

思路：

真是好巧，自己之前由于无聊实现了一把字典树，于是不假思索地写了出来。具体思路可以查看：  

代码：

class Trie {    // 前缀树节点的数据结构    static class Node {        private boolean tag; // 标志当前节点是否为终点 默认为false        private Node[] children;        public Node() {            this.children = new Node[26];        }    }    // 节点内保存什么内容不重要 重要的是边上保存的信息    private Node root; // 记录树根节点    /** Initialize your data structure here. */    public Trie() {        root = new Node();    }        /** Inserts a word into the trie. */    public void insert(String word) {        Node r = root;        for (char c : word.toCharArray()) {            if (r.children[c - 'a'] == null)                r.children[c - 'a'] = new Node();            r = r.children[c - 'a'];        }        r.tag = true; // 设置当前为终点    }        /** Returns if the word is in the trie. */    public boolean search(String word) {        Node r = root;        for (char c : word.toCharArray()) {            if (r.children[c - 'a'] == null)                return false;            r = r.children[c - 'a'];        }        return r.tag;    }        /** Returns if there is any word in the trie that starts with the given prefix. */    public boolean startsWith(String prefix) {        Node r = root;        for (char c : prefix.toCharArray()) {            if (r.children[c - 'a'] == null)                return false;            r = r.children[c - 'a'];        }        return true;    }}

结果：

结论：

巧了。 

转载地址：http://daesi.baihongyu.com/