Java Trie字典树，前缀树-程序员宅基地

Trie查询每个条目的时间复杂度，和字典中一共有多少条无关。

时间复杂度为O（W）

w为查询单词的长度

 

import java.util.TreeMap;

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

	// 返回Trie中存储的单词数量
	public int getSize() {
		return size;
	}

	// 向Trie中添加一个新的单词word
	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是否在Trie中
	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;
	}

//查询是否在Trie中有单词以prefix为前缀
	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;
	}
}

测试：

public class Main {
	public static void Main(String[] args){
		 System.out.println("Pride and Prejudice");
         ArrayList<String> words=new ArrayList<>();
         if(FileOperation.readFile("pride-and-prejudice.txt", words)){

             long startTime = System.nanoTime();
             BSTSet<String> set=new BSTSet<String>();
             for(String word:words)
            	 set.add(word);
             for(String word:words)
            	 set.contains(word);

             long endTime = System.nanoTime();
             double time = (endTime - startTime) / 1000000000.0;

             System.out.println("Total different words: " + set.getSize());
             System.out.println("BSTSet: " + time + " s");
             
             startTime = System.nanoTime();

             Trie trie = new Trie();
             for(String word: words)
                 trie.add(word);

             for(String word: words)
                 trie.contains(word);

             endTime = System.nanoTime();

             time = (endTime - startTime) / 1000000000.0;

             System.out.println("Total different words: " + trie.getSize());
             System.out.println("Trie: " + time + " s");
         }
	}
}

　　search可以搜索文字或正则表达式字符串，字符串只包含字母.或者a-z.

import java.util.TreeMap;

public class WordDictionary {
	public class Node{
	private boolean isWord;
	public TreeMap<Character, Node> next;
	public Node(boolean isWord){
		this.isWord=isWord;
		next=new TreeMap<>();
	}
		public Node() {
			this(false);
		}
	}
	 private  Node root; 
	 
     public WordDictionary(){
    	 root =new Node();
     }

	public void addWord(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);
		}
		cur.isWord = true;
	}
     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;	
		}
	}
}

　　Trie和映射

import java.util.TreeMap;

public class MapSum {
	private class Node{
		public boolean isWord;
		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){
		if(node.next.size()==0)
			return node.value;
		int res=node.value;
		for (char c:node.next.keySet()) 
			res+=sum(node.next.get(c));
		return res;
	}
}