leetCode-208:Implement Trie (Prefix Tree)

问题描述

给定一个前缀树的数据结构和函数定义，要求实现函数内容。题目链接：**点我**

样例输入输出

输入：

[“Trie”, “insert”, “search”, “search”, “startsWith”, “insert”, “search”]

[[], [“apple”], [“apple”], [“app”], [“app”], [“app”], [“app”]]

输出：[null, null, true, false, true, null, true]

解释：

Trie trie = new Trie();
trie.insert(“apple”);
trie.search(“apple”); // return True
trie.search(“app”); // return False
trie.startsWith(“app”); // return True
trie.insert(“app”);
trie.search(“app”); // return True

输入：

[“Trie”, “insert”, “search”,]

[[], [“aaa”], [“bbb”]]

输出：[null, null, false]

解释：

Trie trie = new Trie();
trie.insert(“aaa”);
trie.search(“bbb”); // return False

问题解法

新建一个数据结构用于表示前缀树中的节点，由于题目中有说明字符串只包含 26 个小写字母，因此可以数组来表示孩子节点的数量。代码如下

class Trie
{
    class Node
    {
        char ch;
        Node[] children;
        boolean isEnd;
        public Node(char ch)
        {
            this.ch = ch;
            children = new Node[26];
            isEnd = false;
        }
    }

    Node root;

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

    /** Inserts a word into the trie. */
    public void insert(String word)
    {
        Node current = root;
        for (char ch : word.toCharArray())
        {
            int index = ch - 'a';
            if (current.children[index] == null)
            {
                current.children[index] = new Node(ch);
            }
            current = current.children[index];
        }
        current.isEnd = true;
    }

    /** Returns if the word is in the trie. */
    public boolean search(String word)
    {
        Node current = root;
        for (char ch : word.toCharArray())
        {
            int index = ch - 'a';
            if (current.children[index] == null)
            {
                return false;
            }
            current = current.children[index];
        }

        return current.isEnd;
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix)
    {
        Node current = root;
        for (char ch : prefix.toCharArray())
        {
            int index = ch - 'a';
            if (current.children[index] == null)
            {
                return false;
            }
            current = current.children[index];
        }

        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);
 */