Trie

Trie.

import java.util.*;
public class Trie {

	private static final int R = 26;
	
	private static class TrieNode {
		boolean isLeaf; //是否为单词的结尾
		int count; //以此节点为prefix的字符串的个数, 此属性不是必须的
		TrieNode[] childs = new TrieNode[R];
	}
	
	private TrieNode root = new TrieNode();
	private int size;
	
	public int size() {
		return size;
	}
	
	//if the word does not exist in the dict, insert it, mark the leaf node, increment dict size
	public void insert(String word) {
		if(word==null || word.isEmpty() || contains(word)) return;
		TrieNode node = root;
		for(int i=0; i<word.length(); i++) {
			char c = word.charAt(i);
			int j = c - 'a';
			if(node.childs[j] == null) {
				node.childs[j] = new TrieNode();
			}
			node = node.childs[j];
			node.count++;
		}
		
		if(!node.isLeaf) {
			node.isLeaf = true;
			size++;
		}
	}
	
	public boolean contains(String word) {
		TrieNode node = root;
		for(int i=0; i<word.length(); i++) {
			char c = word.charAt(i);
			int j = c - 'a';
			node = node.childs[j];
			if(node == null) return false;
		}
		return node.isLeaf;
	}
	
	// 1. Key may not be there in trie. Delete operation should not modify trie.
	// 2. Key present as unique key (no part of key contains another key (prefix),
	//    nor the key itself is prefix of another key in trie). Delete all the nodes.
	// 3. Key is prefix key of another long key in trie. Unmark the leaf node.
	// 4. Key present in trie, having at least one other key as prefix key. Delete
	//    nodes from end of key until first leaf node of longest prefix key.
	public boolean delete(String word) {
		if(word==null || word.isEmpty()) return false;
		return delete(root, word, 0);
	}
	
	private boolean delete(TrieNode node, String word, int d) {
		if(node == null) return false;
		if(d == word.length()) {
			if(node.isLeaf) {
				node.isLeaf = false;
				size--;
				return true;
			}
			return false;
		} 
		int k = word.charAt(d) - 'a';
		TrieNode next = node.childs[k];
        boolean ok = delete(next, word, d+1);
        if(ok && --next.count == 0) {
    		node.childs[k] = null;
        }
        return ok;
	}
	
	// yet another method of delete
	public void remove(String word) {
		if(word == null || word.isEmpty()) return;
		remove(root, word, 0);
	}
	
	private TrieNode remove(TrieNode node, String word, int d) {
		if(node == null) return null;
		if(d == word.length()) {
			if(node.isLeaf) {
				node.isLeaf = false;
				size--;
			}
		} else {
			int k = word.charAt(d) - 'a';
			node.childs[k] = remove(node.childs[k], word, d+1);
		}
		for (int i = 0; i < R; i++)
            if (node.childs[i] != null)
                return node;
		return null;
	}
	
	public List<String> words() {
		return wordsWithPrefix("");
	}
	
	public List<String> wordsWithPrefix(String prefix) {
		List<String> list = new ArrayList<>();
		TrieNode node = root;
		for(int i=0; i<prefix.length(); i++) {
			node = node.childs[prefix.charAt(i) - 'a'];
		}
		StringBuilder sb = new StringBuilder(prefix);
		collect(node, sb, list);
		return list;
	}
	
	private void collect(TrieNode node, StringBuilder prefix, List<String> list) {
		if(node == null) return;
		if(node.isLeaf) list.add(prefix.toString());
		for(int i=0; i<R; i++) {
			prefix.append((char)(i+'a'));
			collect(node.childs[i], prefix, list);
			prefix.deleteCharAt(prefix.length()-1);
		}
	}
	
	public String longestPrefixOf(String query) {
        int length = longestPrefixOf(root, query, 0, 0);
        return query.substring(0, length);
    }

    private int longestPrefixOf(TrieNode x, String query, int d, int length) {
        if (x == null) return length;
        if (x.isLeaf) length = d;
        if (d == query.length()) return length;
        char c = query.charAt(d);
        return longestPrefixOf(x.childs[c-'a'], query, d+1, length);
    }
}

 

Test case:

public static void main(String[] args) {
	String[] words = {"the", "a", "there", "answer", "any", "by", "bye", "their", "grass"};
	Trie trie = new Trie();
	for (String word : words) {
		trie.insert(word);
	}
	System.out.println(trie.longestPrefixOf("an"));
	System.out.println(trie.wordsWithPrefix("an"));
	System.out.println(trie.size());
	System.out.println(trie.contains("the"));
	System.out.println(trie.contains("they"));
	System.out.println(trie.contains("by"));
	System.out.println(trie.contains("byn"));
	System.out.println(trie.contains("any"));
	trie.remove("any");
	System.out.println("delete ans:" + trie.delete("ans"));
	System.out.println(trie.contains("any"));
	System.out.println(trie.contains("answer"));
	trie.remove("answer");
	System.out.println(trie.contains("answer"));
	trie.remove("by");
	System.out.println(trie.contains("by"));
	System.out.println("delete by:" + trie.delete("by"));
	System.out.println(trie.contains("bye"));
	System.out.println(trie.size());
}

 

References:

http://algs4.cs.princeton.edu/52trie/TrieST.java.html

http://www.geeksforgeeks.org/trie-delete/