字典树（前缀树）- TrieTree

基本概念

字典树是一种有序的树状结构，每个节点表示字符与字符串。字典树可以合并储存有相同前缀的字符串。常用于解决前缀匹配和字串查找的问题。是一种牺牲空间换取时间的做法。

• 插入 字串长度的时间 插入一个新单词
• 查找 单词长度的时间 查找是否存在某单词 查找是否存在某前缀

实现

• 通过HashMap实现子节点

class TrieNode {
    String word;
    HashMap<Character, TrieNode> next;
​
    public TrieNode() {
        next = new HashMap<>();
    }
}
​
class TrieTree {
    public TrieNode root;
​
    public TrieTree(TrieNode root) {
        this.root = root;
    }
​
    public void insert(String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            if (!node.next.containsKey(word.charAt(i)))
                node.next.put(word.charAt(i), new TrieNode());
            node = node.next.get(word.charAt(i));
        }
        node.word = word;
    }
​
    public String search(String prefix) {
        var node = root;
        for (var c : prefix.toCharArray()) {
            if (!node.next.containsKey(c))
                return "";          
            node = node.next.get(c);
        }
        return node.word;
    }
}

• 通过数组实现子节点

class TrieNode {
    String word;
    TrieNode[] next;
​
    public TrieNode() {
        next = new TrieNode[26];
    }
}
​
class TrieTree {
    public TrieNode root;
​
    public TrieTree(TrieNode root) {
        this.root = root;
    }
​
    public void insert(String word) {
        var node = root;
        for (var i = 0; i < word.length(); i++) {
            if (node.next[word.charAt(i) - 'a'] == null) 
                node.next[word.charAt(i) - 'a'] = new TrieNode();
            node = node.next[word.charAt(i) - 'a'];
        }
        node.word = word;
    }
​
    public String search(String prefix) {
        var node = root;
        for (var c : prefix.toCharArray()) {
            if (node.next[c - 'a'] == null) 
                return "";
            node = node.next[c - 'a'];
        }
        return node.word;
    }
}