字典树

字典树(前缀树)

• 查询每个条目的时间复杂度和字典中一共有多少条目无关
• 时间复杂度为O(w)w为查询单词的长度
• 每个节点有若干个指向下个节点的指针
• 考虑不同的语言,不同的情境

字典树的实现

public class Trie{

    private class Node{
        
        public boolean isWord;

        public TreeMap<Character, Node> next;

        public Node(boolean isWord){
            this.isWord = isWord;
            next = new TreeMap<>();
        }

        public Node(){
            this(false);
        }
    }

    private Node root;

    private int size;

    public Trie(){
        root = new Node();
        size = 0;
    }

    // 获得单词数量
    public int getSize(){
        return size;
    }

    // 添加一个新的单词
    public void add(String word){
        Node cur = root;
        for(int i=0;i<word.length();i++){
            char c = word.charAt(i);
            if(cur.next.get(c)==null){
                cur.next.put(c,new Node());
            }
            cur = cur.next.get(c);
        }
        if(!cur.isWord){
            cur.isWord = true;
            size++;
        }
    }

    // 查询单词word
    public boolean contains(String word){
        Node cur = root;
        for(int i=0;i<word.length();i++){
            char c = word.charAt(i);
            if(cur.next.get(c)==null){
                return false;
            }
            cur = cur.next.get(c);
        }
        return cur.isWord;
    }

    // 前缀搜索
    public boolean isPrefix(String prefix){
        Node cur = root;
        for(int i=0;i<prefix.length();i++){
            char c = prefix.charAt(i);
            if(cur.next.get(c)==null){
                return false;
            }
            cur = cur.next.get(c);
        }
        return true;
    }
}

前缀树的应用

• 实现Trie(前缀树)
• 添加与搜索单词-数据结构设计

public boolean search(String word){
    return match(root,word,0);
}

private boolean match(Node node,String word,int index){
    if(index == word.length()){
        return node.isWord;
    }
    char c = word.charAt(index);
    if(c!='.'){
        if(node.next.get(c)==null){
            return false;
        }
        return match(node.next.get(c),word,index+1);
    }else{
        for(char nextChar : node.next.keySet()){
            if(match(node.next.get(nextChar),word,index+1)){
                return true;
            }
        }
        return false;
    }
}

• Map Sum Pairs

class MapSum{

    private class Node{
        
        public int value;

        public TreeMap<Character, Node> next;

        public Node(int value){
            this.value = value;
            next = new TreeMap<>();
        }

        public Node(){
            this(0);
        }
    }

    private Node root;

    public MapSum(){
        root = new Node();
    }

    public void insert(String word,int val){
        Node cur = root;
        for(int i=0;i<word.length();i++){
            char c = word.charAt(i);
            if(cur.next.get(c)==null){
                cur.next.put(c,new Node());
            }
            cur = cur.next.get(c);
        }
        cur.value = val;
    }

    public int sum(String prefix){
        Node cur = root;
        for(int i=0;i<prefix.length();i++){
            char c = prefix.charAt(i);
            if(cur.next.get(c)==null){
                return 0;
            }
            cur = cur.next.get(c);
        }
        return sum(cur);
    }

    private int sum(Node node){
        int res = node.value;
        for(char c : node.next.keySet()){
            res+=sum(node.next.get(c));
        }
        return res;
    }
}

扩展

• 删除操作
• 局限性:空间(压缩字典树)
• 字符串模式识别:后缀树