需求

• 如何判断一堆不重复的字符串是否以某个前缀开头?
  • 用Set\Map存储字符串
  • 遍历所有字符串进行判断
  • 时间复杂度O(n)
• 有没有更优的数据结构实现前缀搜索?

Trie

• Trie 也叫做字典树、前缀树（Prefix Tree）、单词查找树
• Trie 搜索字符串的效率主要跟字符串的长度有关
• 假设使用 Trie 存储 cat、dog、doggy、does、cast、add 六个单词

接口设计

int size();
boolean isEmpty();
void clear();
boolean contains(String str);
void add(String str);
void remove(String str);
boolean starsWith(String prefix);

int size();
boolean isEmpty();
void clear();
boolean contains(String str);
V add(String str, V value);
V remove(String str);
boolean starsWith(String prefix)

这里提供两套接口，这里选择第二套。

代码实现

Node设计

private static class Node<V> {
    HashMap<Character, Node<V>> children;
    V value;
    boolean word; // 是否为单词的结尾（是否为一个完整的单词）
}

clear get contains

public void clear() {
    size = 0;
    root = null;
}

public V get(String key) {
    Node<V> node = findNode(key);
    return node == null ? null :node.value;
}

public boolean contains(String key) {
    return findNode(key) != null;
}

private Node<V> findNode(String key){
    if(root == null) return null;
    
    keyCheck(key);
    Node<V> node = root;
    int len = key.length();
    for(int i = 0;i < len;i++) {
        char c = key.charAt(i);
        node = node.getChildren().get(c);
        if(node == null) return null;
    }
    return node.word ? node : null;
}

private void keyCheck(String key) {
    if (key == null || key.length() == 0) {
        throw new IllegalArgumentException("key must not be empty");
    }
}

private static class Node<V> {
    HashMap<Character, Node<V>> children;
    V value;
    boolean word; // 是否为单词的结尾（是否为一个完整的单词）
    
    public HashMap<Character, Node<V>> getChildren() {
        return children == null ? (children = new HashMap<>()) : children;
    }
}

findNode方法遍历传递进来的key的每个字符，然后从根节点出发拿到key的某个字符有没有对应的节点，如果对应的节点是空就意味着不存在直接返回null，如果存在就进入下一个循环继续找，如果key的每个字符都找完了，还是不为null，就判断node的节点是否是结束节点，是就返回该节点，否则返回null。

get方法

public V add(String key, V value) {
    keyCheck(key);
    
    // 创建根节点
    if (root == null) {
        root = new Node<>();
    }
    
    Node<V> node = root;
    int len = key.length();
    for(int i = 0;i < len;i++) {
        char c = key.charAt(i);
        Node<V>  childNode = node.getChildren().get(c);
        if(childNode == null) {
            childNode = new Node<>();
            node.getChildren().put(c, childNode);
        }
        node = childNode;
    }
    
    if (node.word) { // 已经存在这个单词
        V oldValue = node.value;
        node.value = value;
        return oldValue;
    }
    
    // 新增一个单词
    node.word = true;
    node.value = value;
    size++;
    return null;
}

startsWith方法

public boolean startsWith(String prefix) {
    if(root == null) return false;
    
    keyCheck(prefix);
    Node<V> node = root;
    int len = prefix.length();
    for(int i = 0;i < len;i++) {
        char c = prefix.charAt(i);
        node = node.getChildren().get(c);
        if(node == null) return false;
    }
    return true;
}

代码调整

这里将Node类的getChildren方法去掉

private static class Node<V> {
    HashMap<Character, Node<V>> children;
    V value;
    boolean word; // 是否为单词的结尾（是否为一个完整的单词）
}

public V get(String key) {
    Node<V> node = findNode(key);
    return node == null && node.word ? node.value : null;
}

public boolean contains(String key) {
    Node<V> node = findNode(key);
    return node != null && node.word;
}

public V add(String key, V value) {
    keyCheck(key);
    
    // 创建根节点
    if (root == null) {
        root = new Node<>();
    }
    
    Node<V> node = root;
    int len = key.length();
    for(int i = 0;i < len;i++) {
        char c = key.charAt(i);
        boolean emptyChildren = node.children == null;
        Node<V> childNode = emptyChildren ? null : node.children.get(c);
        if(childNode == null) {
            childNode = new Node<>();
            node.children = emptyChildren ? new HashMap<>() : node.children;
            node.children.put(c, childNode);
        }
        node = childNode;
    }
    
    if (node.word) { // 已经存在这个单词
        V oldValue = node.value;
        node.value = value;
        return oldValue;
    }
    
    // 新增一个单词
    node.word = true;
    node.value = value;
    size++;
    return null;
}

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

private Node<V> findNode(String key){
    if(root == null) return null;
    
    keyCheck(key);
    Node<V> node = root;
    int len = key.length();
    for(int i = 0;i < len;i++) {
        if (node == null || node.children == null || node.children.isEmpty()) return null;
        char c = key.charAt(i);
        node = node.children.get(c);
    }
    return node;
}

remove方法

为了实现remove方法，我们可以在Node类里增加character字段和构造方法

private static class Node<V> {
    Node<V> parent;
    HashMap<Character, Node<V>> children;
    Character character;
    V value;
    boolean word; // 是否为单词的结尾（是否为一个完整的单词）
    
    public Node(Node<V> parent) {
        this.parent = parent;
    }
}

public V remove(String key) {
    // 找到最后一个节点
    Node<V> node = findNode(key);
    // 如果不是单词结尾，不用作任何处理
    if(node == null || !node.word) return null;
    size--;
    V oldValue = node.value;
    
    // 如果还有子节点
    if (node.children != null && !node.children.isEmpty()) {
        node.word = false;
        node.value = null;
        return oldValue;
    }
    
    // 如果没有子节点
    Node<V> parent = null;
    while ((parent = node.parent) != null) {
        parent.children.remove(node.character);
        if (parent.word || !parent.children.isEmpty()) break;
        node = parent;
    }
    return oldValue;
}

总结

1. Trie 的优点：搜索前缀的效率主要跟前缀的长度有关
2. Trie 的缺点：需要耗费大量的内存，因此还有待改进