LeetCode208.实现Trie(前缀树)

我一开始想题目叫前缀树，是要用树吗？但是不知道用树怎么写，然后我就花了10多分钟，用了HashMap解了。map的key是word，value是一个放了word的所有前缀的set，这样search方法就非常简单了，只要看hashmap里面有没有这个key就行，startsWith方法就很垃圾了，我遍历了所有的value，如果其中一个value中有这个前缀就返回true，遍历完了返回false，以下是我的代码：

class Trie {
    private HashMap<String, Set<String>> map;
    public Trie() {
       map = new HashMap<>();
    }
    
    public void insert(String word) {
     int n = word.length();
     Set<String> set = new HashSet<>();
     int i = n;
     while(i>=0){
      String str = word.substring(0,i);
      set.add(str);
      i--;
     }
     map.put(word, set);
    }
    
    public boolean search(String word) {
      return map.containsKey(word);
    }
    
    public boolean startsWith(String prefix) {
        Set keyset = map.keySet();
        Iterator iterator = keyset.iterator();
        while(iterator.hasNext()){
            String key = (String)iterator.next();
            if(map.get(key).contains(prefix)){
                return true;
            }
        }
       return false;
    }
}

?我这种方法根树没有半毛钱关系，效率极低，看看官方题解的做法吧。

题解是真宗用的字典树，效率非常高。先上题解代码：

class Trie {
    private Trie[] children;
    private boolean isEnd;

    public Trie() {
        children = new Trie[26];
        isEnd = false;
    }
    
    public void insert(String word) {
        Trie node = this;
        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            int index = ch - 'a';
            if (node.children[index] == null) {
                node.children[index] = new Trie();
            }
            node = node.children[index];
        }
        node.isEnd = true;
    }
    
    public boolean search(String word) {
        Trie node = searchPrefix(word);
        return node != null && node.isEnd;
    }
    
    public boolean startsWith(String prefix) {
        return searchPrefix(prefix) != null;
    }

    private Trie searchPrefix(String prefix) {
        Trie node = this;
        for (int i = 0; i < prefix.length(); i++) {
            char ch = prefix.charAt(i);
            int index = ch - 'a';
            if (node.children[index] == null) {
                return null;
            }
            node = node.children[index];
        }
        return node;
    }
}

?它这个树的结构非常巧妙，节点Trie表示一个小写字母，每个节点都包含一个标致位boolean isEnd,表示这个小写字母是不是某个单词的结束字母，还包含一个节点数组Trie[] childern，children[0]表示‘a’..children[25]表示‘z’。

所以比如apple这个单词可以通过字典树表示如下：

?如果再往里面加两个单词，"app"和"yel"就会变成这样：

p的isEnd变成了true，加了一个单词“yel”，这样就非常方便查找了。

public Trie() {
        children = new Trie[26];
        isEnd = false;
    }

通过构造方法我们可以看出，节点创建的时候它的isEnd是false，childre只是创建了一个数组容器，数组里面的节点是没有创建的。

public void insert(String word) {
        Trie node = this;
        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            int index = ch - 'a';
            if (node.children[index] == null) {
                node.children[index] = new Trie();
            }
            node = node.children[index];
        }
        node.isEnd = true;
    }

insert方法非常简单，就是遍历这个word，把它的每个字母往后面添加，最后一个字母的isEnd设置成true。

private Trie searchPrefix(String prefix) {
        Trie node = this;
        for (int i = 0; i < prefix.length(); i++) {
            char ch = prefix.charAt(i);
            int index = ch - 'a';
            if (node.children[index] == null) {
                return null;
            }
            node = node.children[index];
        }
        return node;
    }

searchPrefix()方法作为一个辅助方法，作用是找到传进来的这个单词的最后一个字母。

 public boolean search(String word) {
        Trie node = searchPrefix(word);
        return node != null && node.isEnd;
    }

search()调用searchPrefix()方法拿到单词的最后一个字母节点，如果这个节点不为空并且是结束，返回true。

 public boolean startsWith(String prefix) {
        return searchPrefix(prefix) != null;
    }

?startsWith()方法调用searchPrefix()方法找到前缀的最后一个字母节点，只要这个节点不为空就返回true。

这个字典树的方法是非常的巧妙。