题解 | #字典树的实现#

Java HashMap 实现字典树

import java.util.*;


public class Solution {
    public String[] trieU (String[][] operators) {
        // write code here
        String[] res = new String[0];
        if(operators==null||operators.length==0) return res;
        int len = 0;
        for(String[] op : operators){
            if(op[0].equals("3")||op[0].equals("4")) len++;
        }
        res = new String[len];
        Trie trie = new Trie();
        int index = 0;

        for(String[] op : operators){
            switch(op[0]){
                case "1":
                    trie.insert(op[1]);
                    break;
                case "2":
                    trie.delete(op[1]);
                    break;
                case "3":
                    res[index++] = trie.find(op[1])? "YES":"NO";
                    break;
                case "4":
                    String num = String.valueOf(trie.prefix(op[1]));
                    res[index++] = num;
                    break;
                default:
            }

        }
        return res;
    }
}

class TrieNode{
    Map<Character, TrieNode> map;
    boolean isEnd;
    int preCount;

    public TrieNode(){
        this.map = new HashMap();
        this.isEnd = false;
        this.preCount = 0;
    }
}

class Trie{
    TrieNode root;
    public Trie(){
        this.root = new TrieNode();
    }

    public void insert(String str){
        TrieNode cur = root;
        for(char c : str.toCharArray()){
            if(!cur.map.containsKey(c)) cur.map.put(c, new TrieNode());
            cur = cur.map.get(c);
            cur.preCount++;
        }
        cur.isEnd = true;
    }

    public boolean find(String str){
        TrieNode cur = root;
        for(char c : str.toCharArray()){
            if(!cur.map.containsKey(c)) return false;
            cur = cur.map.get(c);
        }
        return cur.isEnd;
    }

    public void delete(String str){
        if(!find(str)) return;
        TrieNode cur = root;
        for(char c : str.toCharArray()){
            cur = cur.map.get(c);
            cur.preCount--;
        }
        if(cur.preCount==0) cur.isEnd=false;
    }

    public int prefix(String str){
        TrieNode cur = root;
        for(char c : str.toCharArray()){
            if(!cur.map.containsKey(c)) return 0;
            cur = cur.map.get(c);
        }
        return cur.preCount;
    }
}