54、图论-实现Trie前缀树

 思路：

主要是构建一个trie前缀树结构。如果构建呢？看题意，应该当前节点对象下有几个属性：

1、next节点数组

2、是否为结尾

3、当前值

代码如下：

class Trie {

    class Node {
        boolean end;
        Node[] nexts;

        public Node() {
            end = false;
            nexts = new Node[26];
        }
    }

    public Node root;

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

    public void insert(String word) {
        if (word == null) {
            return;
        }
        char[] chs = word.toCharArray();
        Node node = root;
        int path;
        for (int i = 0; i < chs.length; i++) {
            path = chs[i] - 'a';
            if (node.nexts[path] == null) {
                node.nexts[path] = new Node();
            }
            node = node.nexts[path];
        }
        node.end = true;
    }

    public boolean search(String word) {
        if (word == null) {
            return false;
        }
        char[] chs = word.toCharArray();
        Node node = root;
        int path;
        for (int i = 0; i < chs.length; i++) {
            path = chs[i] - 'a';
            if (node.nexts[path] == null) {
                return false;
            }
            node = node.nexts[path];
        }
        return node.end;
    }

    public boolean startsWith(String prefix) {
        if (prefix == null) {
            return false;
        }
        char[] chs = prefix.toCharArray();
        int path;
        Node node = root;
        for (int i = 0; i < chs.length; i++) {
            path = chs[i] - 'a';
            if (node.nexts[path] == null) {
                return false;
            }
            node = node.nexts[path];
        }
        return true;
    }
}