208. Implement Trie (Prefix Tree)

题目描述和难度

  • 题目描述:

实现一个 Trie (前缀树),包含 insertsearch, 和 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 构成的。
  • 保证所有输入均为非空字符串。

思路分析

求解关键:前缀树是一种高级的数据结构,不过实现起来并不困难。

参考解答

参考解答1(内部字典使用 Map)

  • 注意:内部类 Node 的访问控制符要声明为 private ,否则不能得到 Accept 。
import java.util.HashMap;

public class Trie {

    private Node root;

    // 只在内部使用,因此访问控制符是 root
    private class Node {
        private boolean isWord;
        // 不要忘记写上构造方法初始化 next 所对应的 Hash 表
        private HashMap<Character, Node> next;

        public Node() {
            this.isWord = false;
            this.next = new HashMap<>();
        }
    }

    /**
     * Initialize your data structure here.
     */
    public Trie() {
        // 根节点不表示任何字符
        root = new Node();
    }

    /**
     * Inserts a word into the trie.
     */
    public void insert(String word) {
        Node curNode = root;
        for (int i = 0; i < word.length(); i++) {
            Character c = word.charAt(i);
            if (!curNode.next.containsKey(c)) {
                curNode.next.put(c, new Node());
            }
            curNode = curNode.next.get(c);
        }
        // 如果之前没有设置过,才设置成 true
        if (!curNode.isWord) {
            curNode.isWord = true;
        }
    }

    /**
     * Returns if the word is in the trie.
     */
    public boolean search(String word) {
        Node curNode = root;
        for (int i = 0; i < word.length(); i++) {
            Character c = word.charAt(i);
            if (curNode.next.containsKey(c)) {
                curNode = curNode.next.get(c);
            } else {
                return false; // 中途就出错了
            }
        }
        return curNode.isWord; // 到了末尾还要判断一下
    }

    /**
     * Returns if there is any word in the trie that starts with the given prefix.
     */
    public boolean startsWith(String prefix) {
        Node curNode = root;
        for (int i = 0; i < prefix.length(); i++) {
            Character c = prefix.charAt(i);
            if (curNode.next.containsKey(c)) {
                curNode = curNode.next.get(c);
            } else {
                return false;
            }
        }
        // 能走完就说明有这个前缀
        return true;
    }

    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("apple");
        boolean search1 = trie.search("apple");// 返回 true
        System.out.println(search1);
        boolean search2 = trie.search("app");     // 返回 false
        System.out.println(search2);
        boolean startsWith = trie.startsWith("app");// 返回 true
        System.out.println(startsWith);
        trie.insert("app");
        boolean search3 = trie.search("app");     // 返回 true
        System.out.println(search3);
    }
}

参考解答2(内部字典使用结点数组)

public class Trie {

    private Node root;

    private class Node {
        private Node[] dict;
        private boolean isWord;

        public Node() {
            dict = new Node[26];
            this.isWord = false;
        }
    }

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

    /**
     * Inserts a word into the trie.
     */
    public void insert(String word) {
        int len = word.length();
        Node curNode = root;
        for (int i = 0; i < len; i++) {
            char curChar = word.charAt(i);
            Node next = curNode.dict[curChar - 'a'];
            if (next == null) {
                curNode.dict[curChar - 'a'] = new Node();
            }
            curNode = curNode.dict[curChar - 'a'];
        }
        if (!curNode.isWord) {
            curNode.isWord = true;
        }
    }

    /**
     * Returns if the word is in the trie.
     */
    public boolean search(String word) {
        int len = word.length();
        Node curNode = root;

        for (int i = 0; i < len; i++) {
            char curC = word.charAt(i);
            Node next = curNode.dict[curC - 'a'];
            if (next == null) {
                return false;
            } else {
                curNode = next;
            }
        }
        return curNode.isWord;
    }

    /**
     * Returns if there is any word in the trie that starts with the given prefix.
     */
    public boolean startsWith(String prefix) {
        int len = prefix.length();
        Node curNode = root;
        for (int i = 0; i < len; i++) {
            char curC = prefix.charAt(i);
            Node next = curNode.dict[curC - 'a'];
            if (next == null) {
                return false;
            } else {
                curNode = next;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("helloworld");
        boolean startsWith = trie.startsWith("hello");
        System.out.println(startsWith);
        boolean search1 = trie.search("helloworld");
        System.out.println(search1);

        boolean search2 = trie.search("hello");
        System.out.println(search2);
    }
}

本篇文章的地址为 https://liweiwei1419.github.io/leetcode-solution/leetcode-0208-implement-trie-prefix-tree ,如果我的题解有错误,或者您有更好的解法,欢迎您告诉我 liweiwei1419@gmail.com