题目描述(中等难度)

实现 Trie 数,即前缀树。trie的发明者 Edward Fredkin 把它读作 /ˈtriː/ "tree"。但是,其他作者把它读作/traɪ/"try"

解法一

算作一个高级的数据结构,实现方式可以通过 26 叉树。每个节点存一个字母,根节点不存字母。

"app" "as" "cat" "yes" "year" "you"
              root
          /    |    \
         a     c      y
        / \    |     / \
       p   s   a    e   o
      /        |   / \   \
     p         t  s   a   u
                      |
                      r     
上图中省略了 null 节点,对于第一层画完整了其实是下边的样子, 图示中用 0 代表 null
                                   root
         / | | | | | | | | | | | | | | | | | | | | | | | | \
        a  0 c 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 y  0          
其它层同理

代码的话,我们定义一个节点,每个节点包含一个节点数组,代表 26 个孩子。此外,还需要一个 flag 变量来标记当前节点是否是某个单词的结束。

class TrieNode {
    TrieNode[] children;
    boolean flag;
    public TrieNode() {
        children = new TrieNode[26];
        flag = false;
        //节点初始化为 null
        for (int i = 0; i < 26; i++) {
            children[i] = null;
        }
    }
}

然后只需要实现题目中所需要的三个函数即可。其中 children[0]achildren[1]bchildren[2]c... 依次类推。所以存的时候我们用当前字符减去 a ,从而得到相应的 children 下标。

class Trie {
    class TrieNode {
        TrieNode[] children;
        boolean flag;
        public TrieNode() {
            children = new TrieNode[26];
            flag = false;
            for (int i = 0; i < 26; i++) {
                children[i] = null;
            }
        }
    }

    TrieNode root;

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

    /** Inserts a word into the trie. */
    public void insert(String word) {
        char[] array = word.toCharArray();
        TrieNode cur = root;
        for (int i = 0; i < array.length; i++) {
            //当前孩子是否存在
            if (cur.children[array[i] - 'a'] == null) {
                cur.children[array[i] - 'a'] = new TrieNode();
            }
            cur = cur.children[array[i] - 'a'];
        }
        //当前节点代表结束
        cur.flag = true;
    }

    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        char[] array = word.toCharArray();
        TrieNode cur = root;
        for (int i = 0; i < array.length; i++) {
            //不含有当前节点
            if (cur.children[array[i] - 'a'] == null) {
                return false;
            }
            cur = cur.children[array[i] - 'a'];
        }
        //当前节点是否为是某个单词的结束
        return cur.flag;
    }

    /**
     * Returns if there is any word in the trie that starts with the given
     * prefix.
     */
    public boolean startsWith(String prefix) {
        char[] array = prefix.toCharArray();
        TrieNode cur = root;
        for (int i = 0; i < array.length; i++) {
            if (cur.children[array[i] - 'a'] == null) {
                return false;
            }
            cur = cur.children[array[i] - 'a'];
        }
        return true;
    }

};

只要知道每个节点存字母,路径代表单词,代码就很好写出来了。

前缀树适用于两个场景。

  • 统计每个单词出现的次数,代码的话只需要将上边的 flag 改成 int 类型,然后每次插入的时候计数即可。

    当然,我们用 HashMap 也可以做到,key 是单词,value 存这个单词出现的次数即可。但缺点是,当单词很多很多的时候,受到 Hash 函数的影响,hash 值会经常出现冲突,算法可能退化为 O(n)nkey 的总数。

    而对于前缀树,我们查找一个单词出现的次数,始终是 O(m)m 为单词的长度。

  • 查找某个前缀的单词,最常见的比如搜索引擎的提示、拼写检查、ip 路由等。

results matching ""

    No results matching ""