字典树简易实现

Trie.java

 

import java.util.TreeMap;

public class Trie {


    private static 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;
    }

    /**
     * 向Trie中添加一个单词
     */
    public void insert(String word){
        Node cur = root;
        for(char ch : word.toCharArray()){
            if(cur.next.get(ch) == null){
                cur.next.put( ch, new Node());
            }
            cur = cur.next.get(ch);
        }

        if(! cur.isWord){
            cur.isWord = true;
            size ++;
        }
    }


    public boolean search(String word){
        Node cur = root;
        for(char ch : word.toCharArray()){
            if(cur.next.get(ch) == null){
                return false;
            }
            cur = cur.next.get(ch);
        }
        return cur.isWord;
    }

    public boolean isPrefix(String prefix){
        Node cur = root;
        for(char ch : prefix.toCharArray()){
            if(cur.next.get(ch) == null){
                return false;
            }
            cur = cur.next.get(ch);
        }
        return true;
    }

    public int getSize(){return size;}
}