1、前言

2、思路

此题主要是定义 Node 节点的数据结构，主要是有三个变量，char 类型的 c 表示此节点的字符，isEnd 表示是否是单词结尾，List 类型的 child 表示自己的子节点。

3、代码

class Trie {

    class Node {
        char c;
        boolean isEnd;
        List<Node> children;

        public Node(char c) {
            this.c = c;
            this.isEnd = false;
            this.children = new ArrayList<>();
        }
    }

    private Node head;


    /** Initialize your data structure here. */
    public Trie() {
        head = new Node(' ');
    }

    private Node findNode(Node node, char c){
        if(node == null){
            return null;
        }
        for (Node child : node.children) {
            if(child.c == c){
                return child;
            }
        }
        return null;
    }
    
    /** Inserts a word into the trie. */
    public void insert(String word) {
        Node currentNode = head;
        for (char c : word.toCharArray()) {
            Node node = findNode(currentNode, c);
            if(node == null){
                Node newNode = new Node(c);
                currentNode.children.add(newNode);
                currentNode = newNode;
            }else {
                currentNode = node;
            }
        }

        currentNode.isEnd = true;
    }


    
    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        Node currentNode = head;
        for (char c : word.toCharArray()) {
            Node node = findNode(currentNode, c);
            if(node == null){
                return false;
            }else {
                currentNode = node;
            }
        }

        if(currentNode.isEnd){
            return true;
        }
        return false;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        Node currentNode = head;
        for (char c : prefix.toCharArray()) {
            Node node = findNode(currentNode, c);
            if(node == null){
                return false;
            }else {
                currentNode = node;
            }
        }

        return true;
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */

上面的逻辑其实就是树的层序遍历的思路，所以可以这样改：

import javax.xml.bind.SchemaOutputResolver;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author xushu
 * @create 2020/11/12 10:05 AM
 * @desc
 */
public class Trie {

    class TrieTree{
        private char value;
        private List<TrieTree> children;
        private boolean isEnd;

        public TrieTree(char value, List<TrieTree> children, boolean isEnd) {
            this.value = value;
            this.children = children;
            this.isEnd = isEnd;
        }
    }

    private TrieTree root;

    public Trie() {
        this.root = new TrieTree(' ', new ArrayList<>(), false);
    }

    public void insert(String text){
        TrieTree currentNode = this.root;
        Queue<TrieTree> queue = new LinkedList<>();
        queue.offer(currentNode);
        out : for (char c : text.toCharArray()) {
            while (!queue.isEmpty()){
                TrieTree treeNode = queue.poll();
                for (TrieTree child : treeNode.children) {
                    if(child.value == c){
                        currentNode = child;
                        queue.offer(child);
                        continue out;
                    }
                }

                TrieTree node = new TrieTree(c, new ArrayList<>(), false);
                currentNode.children.add(node);
                queue.offer(node);
                currentNode = node;
                break;
            }
        }
        currentNode.isEnd = true;
    }

    public boolean search(String text){
        TrieTree currentNode = this.root;
        Queue<TrieTree> queue = new LinkedList<>();
        queue.offer(currentNode);
        out : for (char c : text.toCharArray()) {
            while (!queue.isEmpty()){
                TrieTree treeNode = queue.poll();
                for (TrieTree child : treeNode.children) {
                    if(child.value == c){
                        queue.offer(child);
                        currentNode = child;
                        continue out;
                    }
                }
                return false;
            }
        }
        return currentNode.isEnd;
    }

    public boolean startsWith(String text){
        TrieTree currentNode = this.root;
        Queue<TrieTree> queue = new LinkedList<>();
        queue.offer(currentNode);
        out : for (char c : text.toCharArray()) {
            while (!queue.isEmpty()){
                TrieTree treeNode = queue.poll();
                for (TrieTree child : treeNode.children) {
                    if(child.value == c){
                        queue.offer(child);
                        continue out;
                    }
                }
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("apple");
        System.out.println(trie.search("apple"));
        System.out.println(trie.startsWith("app"));
        trie.insert("app");
        System.out.println(trie.search("app"));
    }
}