@[TOC](Leetcode208. 实现Trie(前缀树)[Ｍed] -JAVA)

题目

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

Related Topics 设计 字典树

思路

什么是Trie(前缀树)? 有一批单词，a、an、apple、apply、cat 、can、dog 我们肉眼可以直接看出a前缀的有a,an,apple,apply 这几个单词，以app 为前缀有的apple,apply,以c为前缀的有cat,can 如果让你判断某个单位是否存在列表中，一个个字词再到一个个字符比对显然很没有效率，所以我们建立一个前缀树，如下

　　root(只是一个入口)
   /　 　　
  a    c   d
 /    /   /
n  p   a   o
   /   /  /
  p   t   g
  /
  l
 / 
 e y

当要进行查询时，根据前缀树可以快速的找到对应的单词。 就如同在搜索引擎上，当你打上java，搜索下拉框就会出现以java为前缀的句子，讲到这应该大致明白了。 如何实现？ 其实有点像链表。 我们定义一个类，来表示每个节点，而每个节点的子节点用Map装起来，而 map 的value也是这样的节点类，是不是很像链表。 insert时通过遍历单词的字符,如果存在当前字符就继续向下走，如果不存在就新建节点，将当前字符做为key. 这里注意下要在在node 中使用isEnd来做标记，是否当前节点是一个单词的结束节点。这样就可以找一个完整的单词了。 search时通过遍历单词的字符，每个字符都在当前节点的map里找有没有相关的字符，一旦没有就可以终止了。使用isEnd来判断是否为单词的结束 startWith时，找前缀同search一样，但是不用判断isEnd,找完就结束。 结合代码注释看下吧！

解法

class Trie {

    class Node {
        char c;//前缀字符
        HashMap<Character, Node> subNode = new HashMap<>();//用于装子节点
        boolean isEnd;//一个完整单词的终点
        public Node(char c) {
            this.c = c;
        }
    }

    Node root;

    public Trie() {
        root = new Node( );
    }
    
    public void insert(String word) {
        Node current = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            current.subNode.putIfAbsent(c,new Node(c));//为节点赋值
            current = current.subNode.get(c);//为下个节点连接做准备，选好父节点
        }
        current.isEnd=true;//一个完整的单词结束
    }
    
    public boolean search(String word) {
        Node current = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            Node node = current.subNode.get(c);
            if (node==null) return false;
            current = node;
        }
        return current.isEnd;//需要判断是否是一个单词的终点
    }
    
    public boolean startsWith(String prefix) {
        Node current = root;
        for (int i = 0; i < prefix.length(); i++) {
            char c = prefix.charAt(i);
            Node node = current.subNode.get(c);
            if (node==null) return false;
            current = node;
        }
        return true;//同search一样，只是不用判断是否为一个完整的单词，有前缀即可
    }
}